Guide: Greatest Common Divisor (GCD)
What is GCD?
The greatest common divisor (GCD) is the largest integer that divides two or more integers without a remainder. For example GCD(48, 18) = 6, because 6 is the largest number that divides both 48 and 18 without a remainder. GCD is a fundamental concept in number theory and cryptography.
Euclidean Algorithm
The oldest and most efficient method for calculating GCD is the Euclidean algorithm. It relies on repeated division: GCD(a, b) = GCD(b, a mod b), until b equals 0. For example: GCD(48, 18) → GCD(18, 12) → GCD(12, 6) → GCD(6, 0) = 6. This algorithm is extremely fast and works even for very large numbers.
Properties of GCD
GCD(a, b) * LCM(a, b) = a * b (the product of GCD and LCM equals the product of the numbers). If GCD(a, b) = 1, then a and b are relatively prime. GCD is always less than or equal to the smaller of the two numbers. GCD(0, a) = |a| for any non-zero number a.
Practical Applications
GCD is used to simplify fractions - we divide the numerator and denominator by GCD to get an irreducible fraction. In RSA cryptography, GCD is used to generate encryption keys. In computer science, GCD determines the largest common division of memory or processor resources. In music, GCD can determine common sound intervals for rhythms.
Euclid finds the divisor of two nine-digit numbers in three steps
Finding what two numbers have in common looks like it should require factorising them, and factorising is slow. Euclid's algorithm sidesteps it entirely: gcd(123456789, 987654321) = 9, reached in three divisions. Trial division on the smaller number could have needed 11,111 checks. The algorithm is over two thousand years old and still the one every computer uses.
How it works
- Finds the greatest common divisor of two or more numbers using the Euclidean algorithm.
- Reduces fractions to lowest terms, which is the same operation wearing different clothes.
- Reports the number of steps, since the speed is the whole point.
gcd(a, b) = gcd(b, a mod b), repeated until b = 0 the remaining a is the answer lowest terms: a/b ÷ gcd(a, b) on both parts coprime means gcd = 1 — no common factor at all
Worked example
Euclid on progressively nastier inputs.
- gcd(1071, 462) = 21 in 3 steps
- gcd(123456789, 987654321) = 9 in 3 steps
- gcd(2⁴⁰, 3²⁰) = 1 in 15 steps
- gcd(832040, 514229) = 1 in 28 steps
- that last pair is consecutive Fibonacci numbers — the worst case that exists
Two nine-digit numbers resolve in three divisions. Even the deliberately worst input, a pair of consecutive Fibonacci numbers, takes 28. The step count grows with the number of digits, not with the size of the numbers, which is why the algorithm scales to values with hundreds of digits.
Reading the result
- Consecutive Fibonacci numbers are the proven worst case, and they are worst precisely because each division removes as little as possible. gcd(987, 610) takes 14 steps and gcd(75025, 46368) takes 23 — the count creeps up while the numbers explode.
- Reducing a fraction is a gcd in disguise. 84/126 shares a divisor of 42 and drops to 2/3 in one step; the gcd is exactly how far any fraction can be simplified, and dividing by anything smaller leaves work undone.
- The greatest common divisor and the least common multiple are two halves of one tool, tied by gcd(a,b) × lcm(a,b) = a × b. Having either one gives the other for the cost of a multiplication and a division.
- Euclid's algorithm underpins modern cryptography through its extended form, which also produces the coefficients needed for modular inverses. RSA key generation depends on it, which is a long afterlife for a procedure written down around 300 BC.
Common questions
- Why not just factorise both numbers?
- Because factorising is hard and Euclid is not. Splitting 123456789 into primes is real work; taking three remainders is not. The security of RSA rests on exactly this asymmetry — multiplication and gcd are cheap, factorising is not.
- What does a gcd of 1 mean?
- The numbers are coprime — they share no factor above 1. It does not mean either is prime: 8 and 9 are coprime and neither is prime. It does mean the fraction 8/9 is already in lowest terms and cannot be reduced further.