## Euclidean algorithm, greatest common divisor (GCD), highest common factor (HCF)

This javascript calculator calculates for you the Greatest Common Divisor.

GCD( , ) =

Examples:
GCD(1071,1029)=21
GCD(35,42)=7

## The Euclidean algorithm

```function eucledian(a,b){ // a and b must be postive integers, calculates GCD
if (a ==0){
return(b);
}
while(b > 0){
if (a > b) {
a = a - b;
}else{
b = b - a;
}
}
return(a);
}
```

The following algorithm is a modified version of the original Euclidean algorithm. It requires fewer iterations to come to the result.
```function eucledian_mod(a,b){ // a and b must be postive integers, calculates GCD
while(a > 0 && b > 0){
if (a > b) {
a = a % b; // a modulo b
}else{
b = b % a;
}
}
return(a+b); // either a or b is zero
}
```

## Least Common Multiple (LCM) also called the lowest common multiple or smallest common multiple

The LCM can be calculated using the GCD:
```LCM(a,b)=abs(a*b)/GCD(a,b)

abs(a*b) is the absolute of a times b, (always a positive number)
```

Calculate the LCM

LCM( , ) =

## References

This page is operting system independent. It only requires a javascript capable webbrowser. You can install it locally on your PC, iPhone, Android-phone or netbook just by saving this page on the desktop. The page is optimized for mobile devices.

© Guido Socher, License: GPL, This software is provided without warrenty of any kind.
Version: 2012-12-22