The Euclidean Algorithm

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).

Por qué funciona

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.

Ejemplo resuelto: A first run

Find $\gcd(252, 198)$.

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

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

Ejemplo resuelto: Bigger numbers, few steps

Find $\gcd(2431, 1001)$.

$2431 = 1001 \cdot 2 + 429$
$1001 = 429 \cdot 2 + 143$
$429 = 143 \cdot 3 + 0$
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.)

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

Error común

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$.

Idea clave

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

Fuentes y lecturas

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

Práctica

Se apoya en

Lleva a

Fuentes y lecturas