GCD and Euclid's algorithm

The GCD of two integers is the largest integer dividing both. Factoring them into primes works, but it is slow. Euclid found something far better, twenty-three centuries ago.

The idea behind the algorithm

Everything rests on one simple observation. If a = b q + r (Euclidean division of a by b), then:

GCD(a , b) = GCD(b , r)

Indeed, any common divisor of a and b divides r = a - bq; and conversely, any common divisor of b and r divides a = bq + r. The two pairs therefore have exactly the same common divisors.

And r is strictly smaller than b: one problem is replaced by a smaller one, until the remainder is zero.

The algorithm in action

GCD(1071 , 462):

   1071 = 2 × 462 + 147
    462 = 3 × 147 +  21
    147 = 7 ×  21 +   0     <- zero remainder, stop

   GCD = 21     (the last NON-ZERO remainder)

Three divisions. Prime factorisation would have required factoring 1071 and 462 — far longer, and impractical on large numbers.

Why it is fast

The number of divisions is of the order of the number of digits, not of the size of the integers. The worst case occurs for two consecutive Fibonacci numbers — a result proved by Lamé in 1844, and the first complexity analysis in history.

two 1000-digit numbers  ->  a few thousand divisions

This is why Euclid's algorithm remains, to this day, a basic building block of every cryptographic system.

Useful properties

GCD(a , 0) = a
GCD(a , b) = GCD(b , a)
GCD(ka , kb) = k × GCD(a , b)
GCD(a , b) × LCM(a , b) = a × b

Coprime integers

Two integers a and b are coprime when GCD(a , b) = 1.

Careful: this does not mean they are prime. 8 and 9 are coprime and neither is prime — they simply share no factor.

GCD(8 , 9)  = 1     coprime
GCD(12 , 18) = 6    not coprime

Reducing a fraction to lowest terms is precisely dividing numerator and denominator by their GCD:

   1071        1071/21        51
  ------  =  ----------  =  ------
    462        462/21         22

Summary

• GCD(a , b) = GCD(b , r) where r is the remainder of a by b.
• Euclid's algorithm chains divisions until a zero remainder; the GCD is the last non-zero remainder.
• Its cost depends on the number of digits, not the size of the integers.
• GCD × LCM = a × b.
• a and b are coprime if GCD(a , b) = 1 — without being prime themselves.