Euclidean algorithm

The Euclidean Algorithm to compute the greatest common divisor for two integers a and b (not zero) is based on the following fact:

If r is the remainder when a is divided by b (see the division algorithm), then gcd (a,b)=gcd(b,r).

For example, gcd(356,96) = gcd(96,68) (because 68 = 356 - 3^.96).  Continuing this process of dividing, then continuing with the remainder and divisor, we have

gcd(356,96) = gcd(96,68) = gcd(68,28) = gcd(28,12) = gcd(12,4) = gcd(4,0) = 4.

This ancient algorithm was stated by Euclid in his Elements over 2000 years ago, and is still one of the most efficient ways to find the greatest common divisor of two integers.

The algorithm can be written in pseudo-code as follows

Euclid(a,b) {
  while (b not 0) { 
    interchange(a,b)
    b := b mod a
  }
  return(a)
}

On modern computers the binary gcd algorithm is usually faster even though it takes more (but simpler) steps.

One of the uses of the Euclidean algorithm is to solve the diophantine equation ax+by = c.  This is solvable (for x and y) whenever gcd(a,b) divides c.  If we keep track of the quotients in the Euclidean algorithm while finding gcd(a,b), we can reverse the steps to find x and y.

See Also: LamesTheorem