GCD and number theory

39 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

The greatest common divisor of 48 and 18 is the biggest number that divides both. At school you would factor them: 48 = 2 · 2 · 2 · 2 · 3 and 18 = 2 · 3 · 3, take the shared factors 2 · 3, and get 6. Factoring works for small numbers, but factoring a 12-digit number by trial division means testing up to a million candidates, and factoring is in general a hard problem. We need a way to find the gcd without ever factoring.

Build the structure, one piece at a time

The tool is a single fact about remainders. Divide the bigger number by the smaller: 48 = 2 · 18 + 12. Anything that divides both 48 and 18 must also divide 48 − 2 · 18 = 12, because subtracting multiples of a number you divide cannot create a remainder. And anything that divides 18 and 12 also divides 2 · 18 + 12 = 48. So the pair (48, 18) and the pair (18, 12) have exactly the same common divisors, and therefore the same greatest one.

gcd(a, b) = gcd(b, a mod b)

That rule lets us replace the pair with a smaller pair, over and over, until the second number becomes 0. The state is just two numbers:

1. (48, 18): 48 = 2 · 18 + 12, so the pair becomes (18, 12).
2. (18, 12): 18 = 1 · 12 + 6, so the pair becomes (12, 6).
3. (12, 6): 12 = 2 · 6 + 0, so the pair becomes (6, 0).
4. The second number is 0, and every number divides 0, so the gcd of (6, 0) is 6. Hence gcd(48, 18) = 6.

This is Euclid's algorithm, about 2,300 years old and still the one everybody uses. Two helpers ride along with it. The least common multiple is lcm(a, b) = a · b / gcd(a, b). And when a problem needs all primes up to n, the sieve of Eratosthenes does it: write 2 … n, keep 2 and cross out its multiples, keep the next uncrossed number and cross out its multiples, and so on; what survives is prime.

Why it is correct

The invariant is that the gcd of the current pair equals the gcd of the original pair. We proved the step keeps common divisors identical, so the set of common divisors never changes, and so its maximum never changes. The loop ends because the second number strictly decreases (a remainder is always smaller than the divisor) and cannot go below 0. At the end the pair is (g, 0) and gcd(g, 0) = g.

For the sieve, when you reach an uncrossed number p, every smaller number has already crossed out its multiples, so p has no divisor below it other than 1: it is prime.

Why it is fast

Each Euclid step at least halves one of the numbers. Take a ≥ b. If b ≤ a/2 then the new second number a mod b is less than b ≤ a/2. If b > a/2 then a mod b = a − b < a/2. Either way, after two steps the first number has halved, so the number of steps is at most about 2 · log₂(min(a, b)). For two 18-digit numbers that is under 120 divisions. That is O(log min(a, b)), while factoring would take millions of steps.

The sieve marks each composite once per prime factor; the total work is n · (1/2 + 1/3 + 1/5 + …) over primes, which is O(n log log n), close to linear.

How to recognise it in an interview

Cues: "divides evenly", "common divisor", "reduce the fraction", "repeating unit", "measure exactly k litres with two jugs", or "how many primes below n". Say: "this is a gcd question; Euclid gives it in logarithmic time", or "I need the primes up to n, so I will sieve".

In Greatest Common Divisor of Strings the answer is the prefix of length gcd(len(a), len(b)), after checking that a + b equals b + a. In Water and Jug Problem a target amount is reachable exactly when it is at most the two capacities combined and is a multiple of their gcd. Count Primes is the sieve verbatim.

02The idea in one line

Euclid: gcd(a, b) = gcd(b, a mod b); primes by sieve.

Reach for it when: GCD of strings, count primes, ugly numbers, fraction reduction, water jug.

Cost: O(log min(a,b)) per gcd.

03The walk-through, step by step

The video works one example: Euclid gcd(48, 18). These are its captions in order, so you can follow without the video or check a step you missed.

1. Any common divisor of a and b also divides a − q·b, so the remainder keeps the gcd
2. 48 = 2·18 + 12: cut 18 out of 48 as often as possible
3. Shift: a = 18, b = 12
4. 18 = 1·12 + 6: cut 12 out of 18 as often as possible
5. Shift: a = 12, b = 6
6. 12 = 2·6 + 0: cut 6 out of 12 as often as possible
7. Shift: a = 6, b = 0
8. b reached 0: gcd(48, 18) = 6
9. Each step at least halves one number: O(log min(a, b))

04Asked at Google

8 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Math: Fast exponentiation, Digit-by-digit arithmetic, Random pick and reservoir sampling, Coordinate geometry with hashing.