Pequeño teorema de Fermat

Relojes y restos

La aritmética modular es la aritmética del reloj: en un reloj de 12 horas, 15 es lo mismo que 3. Escribimos $15\equiv 3(\mathrm{mod}12)$. El teorema de Fermat dice que, si $p$ es primo, las potencias se comportan con una regularidad sorprendente. Por ejemplo, con $p=7$ y $a=3$:

Idea de la demostración

Tomemos los números $1,2,\dots ,p-1$ y multipliquémoslos todos por $a$ (con $a$ no divisible por $p$). Los restos de $a,2a,\dots ,(p-1)a$ al dividir entre $p$ resultan ser los mismos números $1,\dots ,p-1$, solo que desordenados. Multiplicando todo:

y como $(p-1)!$ no es divisible por $p$, se puede simplificar y queda $a^{p-1}\equiv 1$.

Potencias gigantes en un segundo

Gracias al teorema, calcular restos de potencias enormes se vuelve sencillo: como $3^6\equiv 1(\mathrm{mod}7)$, en $3^{100}$ solo importa el resto de dividir 100 entre 6.

Dónde se usa hoy

• Criptografía RSA: su generalización, el teorema de Euler $a^{\phi (n)}\equiv 1(\mathrm{mod}n)$, es la razón por la que descifrar un mensaje RSA devuelve el texto original. Cada vez que aparece el candado en el navegador, este teorema está trabajando.
• Test de primalidad: si para algún $a$ resulta $a^{n-1}\not\equiv 1(\mathrm{mod}n)$, entonces $n$ no es primo. Los programas lo usan para descartar candidatos rápidamente al buscar primos de cientos de cifras.

Ojo: el recíproco no vale. El 561 cumple la congruencia para todo $a$ coprimo con él, y sin embargo $561=3\cdot 11\cdot 17$ (es un número de Carmichael).