Euclidean Algorithm (GCD)
Reference for the Euclidean Algorithm: find the GCD of two integers via gcd(a, b) = gcd(b, a mod b).
Includes worked examples and extended GCD.
The Recurrence
The Euclidean Algorithm computes the greatest common divisor of two non-negative integers by repeatedly replacing the larger of the two by the remainder when it is divided by the smaller. The process terminates when the remainder becomes zero — at which point the other number is the GCD.
Base Case
Any integer divides zero, so the GCD of any number with zero is itself.
Variables
| Symbol | Meaning | Unit |
|---|---|---|
| a, b | Two non-negative integers | integer |
| a mod b | Remainder when a is divided by b | integer |
| gcd(a, b) | Greatest common divisor | integer |
Example — gcd(252, 105)
Find the GCD of 252 and 105 using the Euclidean Algorithm.
252 = 2 × 105 + 42 → gcd(252, 105) = gcd(105, 42)
105 = 2 × 42 + 21 → gcd(105, 42) = gcd(42, 21)
42 = 2 × 21 + 0 → gcd(42, 21) = 21
gcd(252, 105) = 21
Check: 252 / 21 = 12 and 105 / 21 = 5. Both integers, so 21 divides both. And 12 and 5 share no common factor greater than 1, so 21 is the greatest.
Example — gcd(48, 18)
Find gcd(48, 18).
48 = 2 × 18 + 12 → gcd(48, 18) = gcd(18, 12)
18 = 1 × 12 + 6 → gcd(18, 12) = gcd(12, 6)
12 = 2 × 6 + 0 → gcd(12, 6) = 6
gcd(48, 18) = 6
Extended Euclidean Algorithm
The extended algorithm finds not only the GCD but also integer coefficients s and t such that a × s + b × t = gcd(a, b). This is the key step for computing modular multiplicative inverses, used throughout cryptography.
Worked Extended Example
Find s and t such that 252 × s + 105 × t = 21.
From 252 = 2 × 105 + 42: 42 = 252 − 2 × 105
From 105 = 2 × 42 + 21: 21 = 105 − 2 × 42
Substitute: 21 = 105 − 2 × (252 − 2 × 105) = 5 × 105 − 2 × 252
252 × (−2) + 105 × 5 = 21 (verify: −504 + 525 = 21 ✓)
Complexity
The Euclidean Algorithm runs in O(log(min(a, b))) steps. The slowest case is when a and b are consecutive Fibonacci numbers — the algorithm takes exactly one step per Fibonacci index.
| Input size | Maximum steps |
|---|---|
| 10-digit numbers | ~48 |
| 100-digit numbers | ~480 |
| 1000-digit numbers (RSA-scale) | ~4,800 |
This logarithmic scaling is what makes Euclidean-based cryptography practical even with very large numbers.
When to Use It
- Reducing fractions to lowest terms (divide numerator and denominator by their GCD)
- Solving Diophantine equations (linear ax + by = c)
- Computing modular inverses (extended algorithm) for RSA, ECC, and other cryptographic protocols
- Finding the period of fractions in different bases
- Computing the least common multiple via lcm(a, b) = ab / gcd(a, b)
Why It Works
The algorithm works because any common divisor of a and b also divides their difference, and therefore also divides a mod b (the remainder is a minus some multiple of b). So the set of common divisors is preserved when we replace (a, b) with (b, a mod b), and the GCD is preserved.