The GCD and the Euclidean Algorithm

The greatest common divisor of two numbers is simply the biggest number that goes evenly into both: for 12 and 18 it's 6. The name says exactly that, read backward: a divisor they have in common, the greatest one. It's what you use to reduce a fraction to lowest terms, and it turns out to be the key to dividing in modular arithmetic later in this unit. The formula $\gcd(a, b) = \gcd(b,\; a \bmod b)$ looks cryptic, but it just says: replace the bigger number with the remainder ($a \bmod b$, what's left after dividing $a$ by $b$) and the answer doesn't change. And $\gcd(a, b) = sa + tb$ says the gcd can be built from $a$ and $b$ using whole-number multipliers $s$ and $t$. Two small ideas; bear with them.

You could find a gcd by factoring both numbers, as in the last lesson, but factoring big numbers is slow. Euclid found something much better about 2,300 years ago.

Why the algorithm works. If $a = qb + r$, then any common divisor of $a$ and $b$ also divides $r = a - qb$, and any common divisor of $b$ and $r$ divides $a$. So $(a, b)$ and $(b, r)$ have exactly the same common divisors, and in particular the same greatest one. Notice what that buys you: the pair got smaller, but the answer didn't change. Keep going, and when the remainder hits 0 the last nonzero remainder is the gcd, since $\gcd(g, 0) = g$.

so $\gcd(252, 198) = 18$.

Bézout's identity. Each line above writes a remainder in terms of the two numbers before it. So you can run the steps backward, substituting as you go, and write the gcd as a combination of the original two numbers: $18 = 54 - 36 = 54 - (198 - 3 \cdot 54) = 4 \cdot 54 - 198 = 4 \cdot 252 - 5 \cdot 198$. This extended Euclidean algorithm looks like a curiosity now, but it's exactly how computers find modular inverses, which you'll need two lessons from now.

Speed. The remainders at least halve every two steps, so the algorithm takes at most about twice as many steps as the number of bits in the numbers. That's fast even for numbers hundreds of digits long.

Once you have the gcd, the least common multiple comes for free: $\operatorname{lcm}(a, b) = \frac{ab}{\gcd(a, b)}$. The product $ab$ counts the shared factors twice, and dividing by the gcd removes the extra copy.

Euclid's algorithm, about 2,300 years old, runs inside every RSA implementation to compute private keys, and in every program that reduces fractions.