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

This javascript calculator calculates for you the Greatest Common Divisor.

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

## 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