El teorema: $a^{p-1}\equiv 1 \pmod{p}$

¿Por qué las potencias no crecen "de verdad" módulo un primo?

En capítulos anteriores aprendimos que las sucesiones $a, a^2, a^3, \ldots$ módulo $m$ son eventualmente periódicas. Pero no teníamos una fórmula precisa para el período. El Pequeño Teorema de Fermat responde exactamente esta pregunta cuando $m = p$ es primo: el período divide a $p - 1$.

Dicho de otra manera: si $p$ es primo y $p \nmid a$, entonces $a^{p-1} \equiv 1 \pmod{p}$. La potencia $a^{p-1}$ "regresa a $1$" módulo $p$. Esto es sorprendente: sin importar qué tan grande sea $a$, su $(p-1)$-ésima potencia siempre deja residuo $1$ al dividir por $p$.

Históricamente, Fermat enunció este resultado en 1640 en una carta, sin demostración. Euler fue el primero en publicar una demostración completa en 1736. Hoy es uno de los resultados más usados en olimpiadas de matemáticas y en criptografía.

Enunciado preciso

Sea $p$ un número primo y $a$ un entero tal que $p \nmid a$ (equivalentemente, $\gcd(a, p) = 1$). Entonces:

La hipótesis $p \nmid a$ es esencial. Si $p \mid a$, entonces $a \equiv 0 \pmod p$, de modo que $a^{p-1} \equiv 0 \not\equiv 1 \pmod p$. El teorema simplemente no aplica en ese caso.

Una versión más compacta que funciona para todo entero $a$ (incluso si $p \mid a$) es: $a^p \equiv a \pmod p$. Para $p \nmid a$, dividimos ambos lados por $a$ (que es invertible módulo $p$) y recuperamos la versión original. Para $p \mid a$, ambos lados son $\equiv 0 \pmod p$.

Demostración mediante permutación de residuos

Considera el conjunto $S = \{1, 2, 3, \ldots, p-1\}$. Estos son los $p-1$ residuos no nulos módulo $p$.

Multiplicamos cada elemento por $a$: obtenemos el conjunto $aS = \{a, 2a, 3a, \ldots, (p-1)a\}$. Afirmamos que $aS$ es también un sistema completo de residuos no nulos módulo $p$, es decir, que los elementos de $aS$ son congruentes a $1, 2, \ldots, p-1$ en algún orden.

En efecto: ningún elemento de $aS$ es $\equiv 0 \pmod p$ (porque $p \nmid a$ y $p \nmid k$ para $k \in \{1,\ldots,p-1\}$). Y dos elementos distintos $ka$ y $la$ no pueden ser congruentes módulo $p$ (si $ka \equiv la$, cancelamos $a$ —que es invertible— y obtenemos $k \equiv l$, contradicción). Como hay $p-1$ elementos distintos y no nulos, $aS$ es exactamente una permutación de $S$.

Ahora multiplicamos todos los elementos de $S$ y los de $aS$ y los comparamos: $\prod_{k=1}^{p-1}(ka) \equiv \prod_{k=1}^{p-1} k \pmod p$. El lado izquierdo es $a^{p-1} \cdot (p-1)!$ y el derecho es $(p-1)!$. Como $p \nmid (p-1)!$ (ningún factor de $(p-1)!$ es divisible por $p$), podemos cancelar $(p-1)!$ y obtenemos $a^{p-1} \equiv 1 \pmod p$.

Cálculo práctico: reducción del exponente

La aplicación más directa del teorema es reducir exponentes gigantes módulo $p - 1$. Si $p \nmid a$ y queremos calcular $a^n \pmod p$, escribimos $n = q(p-1) + r$ con $0 \le r < p-1$. Entonces:

$a^n = a^{q(p-1)+r} = (a^{p-1})^q \cdot a^r \equiv 1^q \cdot a^r = a^r \pmod p$.

El residuo $r = n \bmod (p-1)$ es el exponente efectivo. Ejemplo: calcular $3^{100} \pmod 7$. Como $p = 7$, $p - 1 = 6$, y $100 = 16 \cdot 6 + 4$, tenemos $3^{100} \equiv 3^4 = 81 \equiv 4 \pmod 7$.

Atención especial cuando $r = 0$: $a^{p-1} \equiv 1$ (no $a^0 = 1$ trivialmente, sino que el ciclo completo regresa a $1$). Si $n = q(p-1)$, entonces $a^n = (a^{p-1})^q \equiv 1^q = 1 \pmod p$. El resultado sigue siendo correcto.

Ejemplos con primos pequeños

Para $p = 5$: $1^4 = 1$, $2^4 = 16 \equiv 1$, $3^4 = 81 \equiv 1$, $4^4 = 256 \equiv 1 \pmod 5$. Los cuatro residuos no nulos módulo $5$ satisfacen el teorema.

Para $p = 7$: $2^6 = 64 = 9 \cdot 7 + 1 \equiv 1 \pmod 7$. $5^6 = 15625$. Verificamos: $5^2 = 25 \equiv 4$, $5^3 \equiv 20 \equiv 6 \equiv -1$, $5^6 \equiv 1 \pmod 7$.

Para $p = 11$: $7^{10} \equiv 1 \pmod{11}$. No es necesario calcular $7^{10}$ directamente; basta saber que el teorema garantiza el resultado.

En todos los casos, el período de la sucesión de potencias de $a$ módulo $p$ es un divisor de $p - 1$, no necesariamente $p - 1$ en sí. Por ejemplo, $6^2 = 36 \equiv 1 \pmod 7$, así que el período de $6$ módulo $7$ es $2$, que divide a $6 = 7 - 1$.