GCD and the Euclidean Algorithm
Imagine cutting two ropes into equal-length pieces without leaving a remainder. The longest possible piece length is their greatest common divisor, abbreviated gcd. For integers, divisors are exact: 6 divides both 48 and 18, and no larger positive integer does.
Two integers are coprime when their gcd is 1. Coprime is a relationship, not a claim that either number is prime: 8 and 15 are composite but coprime.
Keep the remainder, keep the answer
Euclid's algorithm repeatedly divides and replaces the larger problem by a smaller one:
| Division | Next pair |
|---|---|
| 48=2×18+12 | 18 and 12 |
| 18=1×12+6 | 12 and 6 |
| 12=2×6+0 | Stop: gcd is 6 |
The last nonzero remainder is the gcd. Why does throwing away the quotient work? If a=qb+r, every common divisor of a and b divides r=a-qb. Conversely, every common divisor of b and r divides a=qb+r. Thus:
The common divisors are preserved at each step. The nonnegative remainders strictly decrease until one is zero, so the process terminates. At that point gcd(b,0)=b: every integer divides 0, and the largest divisor of b is b itself.
The small calculation RSA needs
Our later example chooses exponent 3 and totient 40. Euclid gives:
So gcd(3,40)=1. This tells us that multiplication by 3 has an inverse modulo 40. Choosing exponent 5 instead would fail: it shares a factor 5 with 40.
Euclid can be written as a loop or by recursion, with the zero remainder as the base case. Its usefulness is not only speed: keeping track of how each remainder was obtained also produces the coefficients needed for modular inverses.