Euclid and the GCD

By definition, the Greatest Common Divisor (GCD) of two positive integers is the largest integer which divides both integers exactly.

2000 years ago Mr. Euclid developed, or a least published, an algorithm for finding the GCD of two numbers. His version was strictly geometrical and depends on the fact that the the GCD of any two numbers a and b (with a not less than b) is the same as the GCD of the b and the remainder when a is divided by b.

Algebra hadn't been invented when Euclid published his technique, but an algebraic proof looks like this:

Take any two positive integers a and b with b smaller than a. Euclid noted that there are integers r and q such that a=qb + r. (Just divide b into a, then q is the quotient and r is the remainder.)

Any common factor, N, of b and r divides a exactly : (N divides b so it divides qb and it divides r so it divides the sum, qb + r, which is a of course.)

Any common factor, M, of a and b divides r exactly : (r =a-qb so r/M=a/M-qb/M. a/M is an integer and qb/M is an integer so their difference, r/M, is an integer so M divides r.)

Note that all of the N's are M's and all the M's are N's so the largest N must equal the largest M. In other words: GCD(a,b) = GCD(b,r). b is less than a and r is less than b so we can repeat these steps substituting b for a and r for b until r becomes 0. the previous step has a=qb+0 and b is the desired GCD.

A Sample Implementation in Delphi

Function gcd(a,b:integer):integer;
{return greatest common denominator of a and b}

var g,z:integer;
    begin
        g:=b;
        while g<>0 do
        begin
            z:=a mod g;
            a:=g;
            g:=z;
        end;
        result:=a;
    end;

Here's an example of the algorithm in action

A Sample Implementation in Delphi