Euclid's algorithm for greatest common denominator

by Stephen R. Schmitt

Algorithm

Euclid's algorithm determines the greatest common divisor of two integers. It appeared in Euclid's Elements around 300 BC. The algorithm is as follows. Given two natural numbers (integers greater than zero) a and b, calculate t, the remainder after division of a by b. Replace a with b, b with t; repeat until t equals zero.

To be more precise, we can write the operation:

 a 
--- = n, remainder t
 b 

a = b*n + t 

For example, given a = 2232 and b = 327 :

a      b*n     t
------------------
2232 = 327*6 + 270   (2232/327 = 6 with remainder 270)
327  = 270*1 + 57
270  = 57*4  + 42
57   = 42*1  + 15
42   = 15*2  + 12
15   = 12*1  + 3
12   = 3*4   + 0

Zeno source code

• Download Page

program

    var x, y, z : int

    put "numerator and denominator"...
    get x, y
    assert (x > 0) and (y > 0)

    z := gcd( x, y )
    
    put "greatest common denominator = ", z
    put x, "/", y, " = ", x/z, "/", y/z
    
end program

% Euclid's algorithm for greatest common denominator of a / b
function gcd( a, b : int ) : int

    var t : int

    while b > 0
        % display sequence of operations
        put a, tab(7), " = ", b, "*", a div b, " + ", a mod b
        t := a mod b
        a := b
        b := t
    end while

    return a

end function

Sample output

numerator and denominator? 801 24
801     = 24*33 + 9
24      = 9*2 + 6
9       = 6*1 + 3
6       = 3*2 + 0
greatest common denominator = 3
801/24 = 267/8

Reference

Clark University : Euclid's Elements