18.2 Euclidean Algorithm
The Euclidean Algorithm is one of the oldest known algorithms and remains one of the most useful.
18.2 Euclidean Algorithm
The Euclidean Algorithm is one of the oldest known algorithms and remains one of the most useful. It computes the greatest common divisor (GCD) of two integers efficiently, even when the numbers contain hundreds or thousands of digits.
Many advanced algorithms depend directly on GCD computation. Modular inverses, rational arithmetic, cryptographic systems, fraction simplification, number-theoretic transforms, and factorization methods all rely on this fundamental procedure.
The remarkable aspect of the Euclidean Algorithm is its simplicity. A problem that appears to require examining many divisors can instead be solved through repeated remainder computations.
Problem
Given two integers:
a
b
find their greatest common divisor:
gcd(a, b)
The result is the largest positive integer that divides both numbers.
Example:
gcd(24, 18) = 6
because:
Divisors of 24:
1 2 3 4 6 8 12 24
Divisors of 18:
1 2 3 6 9 18
The largest common divisor is:
6
Naive Solution
A straightforward approach checks every possible divisor.
def gcd_naive(a, b):
result = 1
for i in range(1, min(a, b) + 1):
if a % i == 0 and b % i == 0:
result = i
return result
Complexity:
O(min(a,b))
For large numbers this quickly becomes impractical.
Consider:
gcd(123456789, 987654321)
A linear search would require hundreds of millions of checks.
We need something better.
Key Observation
Suppose:
a = bq + r
where:
0 ≤ r < b
Any divisor of both a and b must also divide:
a - bq
But:
a - bq = r
Therefore:
gcd(a,b) = gcd(b,r)
This observation transforms the problem into a smaller one.
The remainder is always smaller than the divisor, so the numbers rapidly decrease.
This is the entire foundation of the Euclidean Algorithm.
Example
Compute:
gcd(48,18)
First division:
48 = 18×2 + 12
Therefore:
gcd(48,18) = gcd(18,12)
Next:
18 = 12×1 + 6
Therefore:
gcd(18,12) = gcd(12,6)
Next:
12 = 6×2 + 0
The remainder becomes zero.
The last nonzero remainder is:
6
Therefore:
gcd(48,18)=6
Recursive Formulation
The observation above naturally produces a recursive algorithm.
If:
b = 0
then:
gcd(a,0)=a
Otherwise:
gcd(a,b)=gcd(b,a mod b)
Python implementation:
def gcd(a, b):
if b == 0:
return a
return gcd(b, a % b)
Example:
print(gcd(48, 18))
Output:
6
The implementation directly mirrors the mathematical proof.
Iterative Formulation
Many production systems prefer an iterative version.
def gcd(a, b):
while b != 0:
a, b = b, a % b
return a
Example:
print(gcd(48,18))
Output:
6
Advantages:
- No recursion depth concerns
- Minimal memory usage
- Often slightly faster
Why It Works
Suppose:
a = bq + r
Every common divisor of a and b divides:
a − bq
which equals:
r
Thus every common divisor of:
(a,b)
is also a common divisor of:
(b,r)
The reverse direction also holds.
Any divisor of:
(b,r)
divides:
bq+r
which equals:
a
Therefore both pairs have exactly the same set of common divisors.
Consequently:
gcd(a,b)=gcd(b,r)
The correctness follows immediately.
Complexity Analysis
The Euclidean Algorithm is surprisingly fast.
The size of the numbers decreases rapidly.
Worst-case inputs occur when the numbers are consecutive Fibonacci numbers.
Example:
gcd(Fₙ₊₁,Fₙ)
Each step produces the previous Fibonacci number.
Even in this worst case, the number of iterations grows logarithmically.
Time complexity:
O(log(min(a,b)))
Space complexity:
O(1)
for the iterative version.
This makes the Euclidean Algorithm one of the most efficient classical algorithms ever discovered.
Binary GCD Algorithm
Division can be relatively expensive on some systems.
The Binary GCD Algorithm uses only:
- subtraction
- comparisons
- bit shifts
Key identities:
If both numbers are even:
gcd(a,b)=2×gcd(a/2,b/2)
If one number is even:
gcd(a,b)=gcd(a/2,b)
or:
gcd(a,b)=gcd(a,b/2)
If both are odd:
gcd(a,b)=gcd(|a−b|,min(a,b))
This method is often used in low-level arithmetic libraries.
GCD of Multiple Numbers
The GCD operation is associative.
gcd(a,b,c)
=
gcd(gcd(a,b),c)
Example:
gcd(24,36,60)
First:
gcd(24,36)=12
Then:
gcd(12,60)=12
Result:
12
Implementation:
from functools import reduce
from math import gcd
nums = [24, 36, 60]
result = reduce(gcd, nums)
print(result)
Fraction Reduction
Fractions are simplified by dividing numerator and denominator by their GCD.
Example:
84/126
Compute:
gcd(84,126)=42
Then:
84/126
=
2/3
This operation appears constantly in rational arithmetic libraries.
Detecting Coprime Numbers
Two numbers are coprime when:
gcd(a,b)=1
Example:
gcd(35,64)=1
Therefore:
35 and 64 are coprime
Coprimality is central to:
- modular arithmetic
- Euler's theorem
- RSA cryptography
- Chinese Remainder Theorem
Practical Applications
Cryptography
RSA key generation repeatedly computes GCD values.
Fraction Arithmetic
Every rational-number implementation simplifies fractions using GCD.
Geometry
Lattice-point algorithms often normalize vectors:
(dx,dy)
by dividing by:
gcd(dx,dy)
Scheduling
Periods align through GCD and LCM calculations.
Hashing
Modular arithmetic frequently requires coprime parameters.
Common Mistakes
Forgetting Zero Cases
Correct identities:
gcd(a,0)=a
gcd(0,a)=a
for positive a.
Returning the Last Remainder
The answer is the last nonzero remainder.
Not the final zero.
Assuming Prime Inputs
The Euclidean Algorithm works for arbitrary integers.
No primality assumptions are required.
Using the Naive Method
A linear divisor search becomes unusable for large inputs.
The Euclidean Algorithm should almost always be preferred.
Takeaway
The Euclidean Algorithm transforms GCD computation from a linear search into a logarithmic-time procedure by repeatedly replacing a pair of integers with a smaller equivalent pair based on remainders. The key identity
gcd(a,b)=gcd(b,a mod b)
preserves all common divisors while rapidly reducing problem size. This algorithm serves as the foundation for modular arithmetic, coprimality testing, rational-number simplification, cryptographic protocols, and many advanced number-theoretic techniques that follow in the remainder of the chapter.