Euclidean algorithm
(another Prime Pages' Glossary entries)
The Prime Glossary
Glossary: Prime Pages: Top 5000:
GIMPS has discovered a new largest known prime number: 282589933-1 (24,862,048 digits)

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) { 
    b := b mod 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

Chris K. Caldwell © 1999-2020 (all rights reserved)