Pequeño Teorema de Fermat

El teorema que hace manejable lo inmenso

El Pequeño Teorema de Fermat (PTF) es quizás el resultado más usado en toda la aritmética modular olímpica. Su enunciado es tan limpio que parece demasiado bueno para ser verdad: si $p$ es primo y $p \nmid a$, entonces $a^{p-1} \equiv 1 \pmod{p}$.

En la práctica esto significa lo siguiente: para calcular $a^k \bmod p$, podemos reducir el exponente $k$ módulo $p-1$. Si $k = q(p-1) + r$, entonces $a^k = (a^{p-1})^q \cdot a^r \equiv 1^q \cdot a^r = a^r \pmod{p}$. Exponentes que antes parecían astronómicos se reducen a algo con a lo sumo $p-2$ dígitos.

Un corolario inmediato, válido para cualquier entero $a$ (incluso si $p \mid a$): $a^p \equiv a \pmod{p}$. Si $p \nmid a$, aplicamos el PTF y multiplicamos por $a$. Si $p \mid a$, ambos lados son $\equiv 0$.

Demostración: la biyección mágica

Considera el conjunto $S = \{1, 2, 3, \ldots, p-1\}$. Fijado $a$ con $p \nmid a$, define la función $f: S \to S$ por $f(x) = ax \bmod p$.

Primero, $f$ está bien definida: si $x \in S$, entonces $ax \not\equiv 0 \pmod{p}$ (pues $p \nmid a$ y $p \nmid x$ y $p$ es primo), así que $f(x) \in \{1, \ldots, p-1\} = S$.

Segundo, $f$ es inyectiva: si $ax \equiv ay \pmod{p}$, como $\gcd(a, p) = 1$ podemos cancelar $a$, obteniendo $x \equiv y \pmod{p}$, es decir $x = y$ (ambos en $S$). Una función inyectiva de un conjunto finito en sí mismo es biyectiva.

Conclusión de la biyección: al multiplicar todos los elementos de $S$ por $a$, obtenemos de nuevo todos los elementos de $S$ (en otro orden). Por lo tanto el producto de todos los elementos de $f(S)$ es igual al de $S$:

Esto es $(a \cdot 1)(a \cdot 2)\cdots(a \cdot (p-1)) \equiv 1 \cdot 2 \cdots (p-1) \pmod{p}$, es decir $a^{p-1} (p-1)! \equiv (p-1)! \pmod{p}$. Como $\gcd((p-1)!, 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}$. Demostración completa.

Aplicación directa: potencias grandes módulo un primo

Queremos calcular $2^{340} \bmod 341$. Observa que $341 = 11 \cdot 31$, así que no es primo. Sin embargo, probemos ciegamente el PTF con $p = 341$: si el PTF valiera para todo $n$ compuesto, tendríamos $2^{340} \equiv 1 \pmod{341}$.

Calculemos por separado módulo $11$ y módulo $31$. Por PTF: $2^{10} \equiv 1 \pmod{11}$ y $2^{30} \equiv 1 \pmod{31}$. Ahora, $340 = 34 \cdot 10$, luego $2^{340} = (2^{10})^{34} \equiv 1 \pmod{11}$. También $340 = \frac{340}{30} \cdot 30 + 10$... espera: $340 = 11 \cdot 30 + 10$, así que $2^{340} = (2^{30})^{11} \cdot 2^{10} \equiv 1^{11} \cdot 2^{10} \pmod{31}$. Y $2^5 = 32 \equiv 1 \pmod{31}$, así que $2^{10} = (2^5)^2 \equiv 1 \pmod{31}$.

Entonces $2^{340} \equiv 1 \pmod{11}$ y $2^{340} \equiv 1 \pmod{31}$. Como $\text{mcm}(11, 31) = 341$, concluimos $2^{340} \equiv 1 \pmod{341}$.

Aquí está la trampa: el hecho de que $2^{340} \equiv 1 \pmod{341}$ parecería indicar que $341$ es primo por el "recíproco" del PTF. Pero $341 = 11 \cdot 31$ es compuesto. Los números compuestos $n$ que satisfacen $2^{n-1} \equiv 1 \pmod{n}$ se llaman pseudoprimos de Fermat en base 2, y $341$ es el menor de ellos. Este es el motivo por el que el recíproco del PTF no vale en general.

Reducción de exponentes con PTF: método sistemático

El procedimiento estándar para calcular $a^k \bmod p$ con $p$ primo es: (1) si $p \mid a$, la respuesta es $0$; (2) si no, calcula $r = k \bmod (p-1)$ y responde $a^r \bmod p$.

Ejemplo: $3^{1000} \bmod 7$. Primo $p=7$, $p-1=6$. Reducimos: $1000 = 166 \cdot 6 + 4$, así $r=4$. Entonces $3^{1000} \equiv 3^4 = 81 \equiv 81 - 11 \cdot 7 = 81 - 77 = 4 \pmod{7}$.

Otro ejemplo: $5^{2026} \bmod 13$. Primo $p=13$, $p-1=12$. Reducimos: $2026 = 168 \cdot 12 + 10$, así $r = 10$. Entonces $5^{2026} \equiv 5^{10} \pmod{13}$. Calculamos $5^2 = 25 \equiv 12 \equiv -1$, $5^{10} = (5^2)^5 \equiv (-1)^5 = -1 \equiv 12 \pmod{13}$.

Este método es completamente mecánico una vez que tienes el PTF. En competencias, reducir exponentes módulo $p-1$ es el primer paso automático cuando el módulo es primo.

El PTF en problemas de divisibilidad y congruencias

Más allá del cálculo, el PTF es una herramienta de demostración. Por ejemplo: demostrar que para todo primo $p$ y entero $a$, $p \mid a^p - a$. Esto es exactamente el corolario $a^p \equiv a \pmod{p}$, válido para todo $a$.

Aplicación olímpica: probar que $42 \mid n^7 - n$ para todo entero $n$. Factorizamos $n^7 - n = n(n^6 - 1) = n(n^2-1)(n^4+n^2+1)$. Pero más elegante: $42 = 2 \cdot 3 \cdot 7$. Por el corolario del PTF, $2 \mid n^2 - n$, $3 \mid n^3 - n$, $7 \mid n^7 - n$. El problema se reduce a mostrar que $n^7 - n$ es divisible por $2$, $3$ y $7$. Para $7$ es directo; para $2$ y $3$ se usa que $n^7 - n = n(n^6-1)$ y los PTF respectivos. En particular $n^7 \equiv n \pmod{7}$ por PTF con $p=7$.

La moral: el PTF convierte muchos problemas de divisibilidad en verificaciones automáticas. Aprende a reconocer la forma $a^p - a$ (o su generalización $a^{p-1} - 1$) dentro de expresiones más complejas.