Algoritmo de Euclides

Factorizar un número grande es difícil, pero dividir es fácil. El algoritmo de Euclides aprovecha que \(\gcd(a,b)=\gcd(b,r)\) cuando \(a=qb+r\): los divisores comunes de \(a\) y \(b\) son exactamente los de \(b\) y \(r\). Se repite hasta que el residuo es 0, y el último residuo no nulo es el resultado. Para \(a=252\) y \(b=105\): \(252=2\cdot105+42\), \(105=2\cdot42+21\), \(42=2\cdot21+0\), de modo que \(\gcd(252,105)=21\).

Termina siempre porque los residuos son enteros no negativos que decrecen estrictamente. Es además muy rápido: cada dos pasos el residuo se reduce al menos a la mitad, por lo que el número de divisiones es proporcional a la cantidad de cifras. El peor caso son dos números de Fibonacci consecutivos: \(\gcd(89,55)\) necesita 9 divisiones, todas con cociente 1. Si \(a<b\), el primer paso solo intercambia los números.

Retrocediendo por las divisiones se obtiene la versión extendida: números enteros \(x,y\) con \(ax+by=\gcd(a,b)\), la identidad de Bézout. Con ella se resuelven ecuaciones diophantinas \(ax+by=c\) y se calculan inversos módulo \(m\), que son la base de la criptografía RSA. Un error frecuente es detenerse en el residuo 0 en lugar de tomar el residuo anterior: el resultado es el último residuo no nulo, es decir, el último divisor.