Number TheoryDivisibility and the Euclidean Algorithm

The Euclidean Algorithm

gcd(a, b) = gcd(b, r), where r is the remainder when a is divided by b; repeat until the remainder is 0.

Not started Jump to practice

In grade 6 you found the greatest common factor by listing factors. That is fine for $12$ and $18$, hopeless for $2431$ and $1001$, and impossible for numbers with hundreds of digits, which cryptography uses every day. Euclid's algorithm, more than 2,000 years old, finds the gcd with a handful of divisions and no factoring at all.

Definition. For integers $a$ and $b$, not both $0$, the greatest common divisor $\gcd(a, b)$ is the largest integer that divides both. Two numbers with $\gcd(a, b) = 1$ are called coprime (or relatively prime).

Why it works

The key fact: if $a = bq + r$, then $\gcd(a, b) = \gcd(b, r)$. Here is why. If $d$ divides $a$ and $b$, it divides $a - bq = r$ (a combination, as in divisibility). If $d$ divides $b$ and $r$, it divides $bq + r = a$. So the pairs $(a, b)$ and $(b, r)$ have exactly the same common divisors, and therefore the same greatest one.

The algorithm. Divide $a$ by $b$ with the division algorithm, then replace $(a, b)$ by $(b, r)$ and repeat. The remainders get strictly smaller and never go below $0$, so eventually one is $0$. Since $\gcd(g, 0) = g$, the last nonzero remainder is the gcd.

Each division cuts the largest possible squares from the rectangle. The last square's side, 18, tiles the whole $252 \times 198$ rectangle: it divides both sides.

Worked example: A first run

Find $\gcd(252, 198)$.
  1. $252 = 198 \cdot 1 + 54$
  2. $198 = 54 \cdot 3 + 36$
  3. $54 = 36 \cdot 1 + 18$
  4. $36 = 18 \cdot 2 + 0$. The remainder is $0$, so stop.
  5. The last nonzero remainder is $18$. Check: $252 = 18 \cdot 14$ and $198 = 18 \cdot 11$.

Answer: $\gcd(252, 198) = 18$.

Worked example: Bigger numbers, few steps

Find $\gcd(2431, 1001)$.
  1. $2431 = 1001 \cdot 2 + 429$
  2. $1001 = 429 \cdot 2 + 143$
  3. $429 = 143 \cdot 3 + 0$
  4. The gcd is $143$. (Indeed $2431 = 11 \cdot 13 \cdot 17$ and $1001 = 7 \cdot 11 \cdot 13$, but the algorithm never needed those factorizations.)

Answer: $\gcd(2431, 1001) = 143$.

Common mistake

Reporting the last quotient, or the final $0$, instead of the last nonzero remainder. In the first example the last line is $36 = 18 \cdot 2 + 0$: the answer is $18$, not $2$ and not $0$. Check any answer by dividing: the gcd must divide both original numbers.
The algorithm is fast. Each remainder is less than half of the number two lines above it, so the number of steps grows only with the number of digits. The slowest inputs are neighboring Fibonacci numbers, where every quotient is $1$.

Two small conventions make the algorithm work for every input. Signs do not matter, so $\gcd(-252, 198) = \gcd(252, 198)$. And $\gcd(a, 0) = |a|$ for $a \neq 0$, since every integer divides $0$. If you start with the smaller number first, the first division simply swaps them: $198 = 252 \cdot 0 + 198$.

Key idea

$\gcd(a, b) = \gcd(b, r)$ when $a = bq + r$. Divide, shift, and repeat; the last nonzero remainder is the gcd.

Practice

Pass with 3 right answers, the last 2 in a row. Each right answer earns 2 XP.

Loading practice…

Builds on

Leads to

Sources and further reading

  • William Stein, Elementary Number Theory: Primes, Congruences, and Secrets (Springer, 2009; free online edition), chapter 1, Prime Numbers (greatest common divisors and the Euclidean algorithm)
  • Lehman, Leighton and Meyer, Mathematics for Computer Science (MIT OpenCourseWare 6.042J), chapter on number theory: the greatest common divisor
@teddyrookbook GitHub