Mathematics.

elementary number theory

The Euclidean Algorithm

Number Theory25 minDifficulty3 out of 10

You should know: divisibility, gcd and lcm

Overview

The Euclidean algorithm is one of the oldest algorithms still in use — it appears in Euclid's Elements (c. 300 BCE) — and computes the greatest common divisor (GCD) of two integers without factoring either of them. Its engine is a single fact: any common divisor of a and b also divides their difference, and more sharply, gcd(a, b) = gcd(b, a mod b). Repeatedly replacing the larger number by the remainder of dividing it by the smaller shrinks the pair quickly; when the remainder hits 0, the last nonzero remainder is the GCD. Because the numbers fall at least geometrically, the algorithm runs in O(log(min(a, b))) division steps — dramatically faster than listing divisors or factoring, which is why it underlies modular inverses, RSA key setup, and continued fractions.

Intuition

Picture tiling an a-by-b rectangle with the largest squares possible. Lay down as many b-by-b squares as fit; a strip of width (a mod b) is left over. Now tile THAT strip the same way. Each leftover strip is smaller than the last, so the process must stop — and the side of the final square that tiles everything exactly is gcd(a, b). The algorithm is just this geometric peeling written arithmetically.

Formal Definition

Definition

For integers a ≥ b > 0, define the remainder sequence r₀ = a, r₁ = b, and rₖ₊₁ = rₖ₋₁ mod rₖ until a zero remainder appears:

gcd⁡(a,b)=gcd⁡(b, a mod b)\gcd(a, b) = \gcd(b,\ a \bmod b)
Reduction step (the whole idea)
rk+1=rk−1−qkrk,0≤rk+1<rkr_{k+1} = r_{k-1} - q_k r_k, \qquad 0 \le r_{k+1} < r_k
Division with remainder
gcd⁡(a,b)=rn where rn+1=0\gcd(a,b) = r_{n} \text{ where } r_{n+1} = 0
Last nonzero remainder is the GCD
gcd⁡(a,b)=ax+by(x,y∈Z)\gcd(a,b) = a x + b y \quad (x, y \in \mathbb{Z})
Bézout's identity (extended algorithm)

Worked Examples

  1. Divide 252 by 105; the remainder replaces the larger number.

    252=2⋅105+42252 = 2\cdot 105 + 42

  2. Now reduce the pair (105, 42).

    105=2⋅42+21105 = 2\cdot 42 + 21

  3. Reduce (42, 21); the remainder is 0, so the last nonzero remainder, 21, is the GCD.

    42=2⋅21+042 = 2\cdot 21 + 0

Answer: gcd(252, 105) = 21.

Practice Problems

Difficulty 2/10

Compute 105 mod 42.

Difficulty 2/10

Compute 1071 mod 462.

Difficulty 5/10

Two gears with 1071 and 462 teeth mesh. Using the Euclidean algorithm, how many teeth apart is the largest tooth-spacing that both gears share (their GCD)?

Quiz

The Euclidean algorithm replaces the pair (a, b) with:
The algorithm terminates and returns the GCD when:
Extending the algorithm (the extended Euclidean algorithm) additionally produces integers x, y satisfying:

Summary

  • gcd(a, b) = gcd(b, a mod b): repeatedly reduce the larger number modulo the smaller.
  • The last nonzero remainder is the GCD; the algorithm runs in O(log min(a,b)) division steps.
  • Extended to track coefficients, it yields Bézout's identity ax + by = gcd(a,b) and hence modular inverses.

References

  1. WebsiteWikipedia — Euclidean algorithm