The oldest nontrivial algorithm
The greatest common divisor of two integers is the largest number dividing both. Euclid's method computes it without factoring, using a simple insight about remainders.
The key fact
Any number that divides both a and b also divides their remainder when a is divided by b. So the common divisors of a and b are exactly the common divisors of b and that remainder. Replacing the larger number by the remainder shrinks the problem while preserving the answer.
The procedure
- Given a and b, compute the remainder of a divided by b.
- Replace a with b and b with that remainder.
- Repeat until the remainder is zero.
- The last nonzero value is the greatest common divisor.
Because the remainder is always smaller than the divisor, the numbers fall rapidly. The number of steps grows only with the number of digits, so even huge inputs finish quickly. Consecutive Fibonacci numbers are the worst case.
Key idea
Euclid replaces the larger number with the remainder repeatedly; common divisors are preserved, and when the remainder hits zero the last value is the greatest common divisor.