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

This javascript calculator calculates for you the Greatest Common Divisor.

GCD( , ) =


The Euclidean algorithm

function eucledian(a,b){ // a and b must be postive integers, calculates GCD
    if (a ==0){
    while(b > 0){
        if (a > b) {
            a = a - b;
            b = b - 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
            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:

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

Calculate the LCM

LCM( , ) =


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