Source : Free On-Line Dictionary of Computing

Euclid's Algorithm
     
         (Or "Euclidean Algorithm") An {algorithm} for
        finding the {greatest common divisor} (GCD) of two numbers.
        It relies on the identity
     
        	gcd(a, b) = gcd(a-b, b)
     
        To find the GCD of two numbers by this algorithm, repeatedly
        replace the larger by subtracting the smaller from it until
        the two numbers are equal.  E.g. 132, 168 -> 132, 36 -> 96, 36
        -> 60, 36 -> 24, 36 -> 24, 12 -> 12, 12 so the GCD of 132 and
        168 is 12.
     
        This algorithm requires only subtraction and comparison
        operations but can take a number of steps proportional to the
        difference between the initial numbers (e.g. gcd(1, 1001) will
        take 1000 steps).
     
        (1997-06-30)