Greatest Common Divisors

Why does a tiny rule from antiquity power the modern internet? Every time your browser shakes hands with a banking site, every time a credit card terminal signs a transaction, every time a Signal message lands on your phone, an algorithm credited to Euclid is running in the background. The greatest common divisor is the largest integer that divides two numbers cleanly, and the Euclidean algorithm for finding it is the oldest non-trivial algorithm still in everyday use. It is fast (logarithmic in the inputs), it is exact, and it is the gateway to Bezout coefficients, modular inverses, RSA key generation, and a dozen other corners of cryptography. Master this one tool and the rest of Chapter 7 falls into place.

The definition, sharpened

For integers $a$ and $b$ not both zero, $d = \gcd(a, b)$ is the unique positive integer satisfying two conditions: (1) $d \mid a$ and $d \mid b$, and (2) every common divisor $c$ of $a$ and $b$ also divides $d$. The second condition is stronger than “$c \leq d$” — it says $d$ is the maximum common divisor in the divisibility order, not merely in size. Two integers with $\gcd(a, b) = 1$ are called coprime (equivalently, relatively prime).

The Euclidean algorithm

The heart of the algorithm is a one-line observation. If $a = bq + r$ with $0 \leq r < b$, then any common divisor of $a$ and $b$ also divides $r = a - bq$, and vice versa. Therefore $\gcd(a, b) = \gcd(b, r)$. Iterate this rewriting and the remainders form a strictly decreasing sequence of non-negative integers, so the process must terminate. The last non-zero remainder is the GCD.

Worked example. $\gcd(252, 105)$: $252 = 105 \cdot 2 + 42$, $105 = 42 \cdot 2 + 21$, $42 = 21 \cdot 2 + 0$. The last non-zero remainder is $21$, so $\gcd(252, 105) = 21$.

Bezout’s identity

For any integers $a, b$ not both zero, there exist integers $s, t$ with $\gcd(a, b) = sa + tb$. The integers $s, t$ are the Bezout coefficients and are not unique — they are recovered by reading the Euclidean algorithm backwards. Back-substituting in the example above: $21 = 105 - 42 \cdot 2 = 105 - (252 - 105 \cdot 2) \cdot 2 = 5 \cdot 105 - 2 \cdot 252$. So $(s, t) = (-2, 5)$. Bezout’s identity is the bridge from the GCD to modular inverses: when $\gcd(a, n) = 1$, the coefficient $s$ in $sa + tn = 1$ is exactly $a^{-1} \pmod{n}$.

(The stepper above visualises an iterative algorithm. Use it as a mental model for stepping through the Euclidean algorithm: each step shrinks the pair $(a, b)$ until the second entry reaches zero.)

Pause and think: Before reading on, predict $\gcd(0, 15)$. (Hint: every integer divides $0$, so the question reduces to: what is the largest divisor of $15$?) Then predict $\gcd(15, 15)$. The pattern that emerges is worth a sentence of explanation in your own words.

Try it

• Predict first: how many division steps does the Euclidean algorithm take on $\gcd(89, 55)$? (Both are Fibonacci numbers — this is the slowest case for inputs of that size.) Then run it and count.
• Compute $\gcd(1071, 462)$ by hand. Find Bezout coefficients $s, t$ such that $\gcd = 1071s + 462t$.
• Prove without a calculator: for any positive integer $n$, $\gcd(n, n+1) = 1$. Use the “subtract one multiple” trick that drives the algorithm.
• Two-step puzzle: compute $\gcd(2^{10} - 1, 2^6 - 1) = \gcd(1023, 63)$. The answer has a clean closed form — can you guess $\gcd(2^m - 1, 2^n - 1)$ in general?

A trap to watch for

The GCD and the least common multiple (LCM) are siblings, not synonyms. $\gcd(a, b)$ is the largest integer dividing both; $\text{lcm}(a, b)$ is the smallest positive integer divisible by both. They satisfy $\gcd(a, b) \cdot \text{lcm}(a, b) = |ab|$, so once you know one you can recover the other — but they are not the same number. A frequent student error is to compute $\gcd(12, 18) = 6$ and report $6$ as “the common multiple,” or to call $\text{lcm}(12, 18) = 36$ “the largest common factor.” If you find yourself unsure which one a problem wants, ask: am I being asked for the biggest divisor (GCD, sits below both) or the smallest multiple (LCM, sits above both)?

What you now know

You can compute $\gcd(a, b)$ in logarithmic time, recover Bezout coefficients by back-substitution, and translate “coprime” into the equation $sa + tb = 1$. In the next section, prime factorisation, Bezout’s identity is the key lemma that proves uniqueness: it is precisely why a prime $p$ dividing a product $ab$ must divide one of the factors, and therefore why every integer has only one factorisation into primes.

References

• Velleman, D. J. (2019). How to Prove It: A Structured Approach (3rd ed.). Cambridge University Press, §7.1.
• Hardy, G. H., Wright, E. M. (2008). An Introduction to the Theory of Numbers (6th ed.). Oxford University Press, ch. 2.
• Niven, I., Zuckerman, H. S., Montgomery, H. L. (1991). An Introduction to the Theory of Numbers (5th ed.). Wiley, ch. 1.
• Rosen, K. H. (2010). Elementary Number Theory (6th ed.). Pearson, ch. 3.
• Knuth, D. E. (1997). The Art of Computer Programming, Vol. 2: Seminumerical Algorithms (3rd ed.). Addison-Wesley, §4.5.2.