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