El Pequeño Teorema de Fermat

Teoría

El Pequeño Teorema de Fermat es una pieza fundamental de la teoría de números elemental y la aritmética modular. Te da una herramienta muy poderosa para simplificar cálculos que involucran potencias muy grandes módulo un número primo.

El teorema tiene un montón de aplicaciones:

• Calcular potencias grandes módulo $p$ de forma eficiente
• Encontrar inversos modulares
• Pruebas de primalidad (aunque el recíproco no siempre es cierto)
• Demostrar resultados de divisibilidad
• Criptografía (es la base del algoritmo RSA)

Puedes ver este teorema como un caso especial del teorema de Euler, que es la generalización para módulos compuestos.

Fórmulas Clave

El Pequeño Teorema de Fermat (Forma Estándar):

Si $p$ es primo y $\gcd(a, p) = 1$, entonces: $$a^{p-1} \equiv 1 \pmod{p}$$

Forma Alternativa:

Para cualquier entero $a$ y primo $p$: $$a^p \equiv a \pmod{p}$$

(Esta forma funciona incluso si $p \mid a$).

Inverso Modular usando Fermat:

Si $p$ es primo y $\gcd(a, p) = 1$: $$a^{-1} \equiv a^{p-2} \pmod{p}$$

Reducción de Exponentes:

Para un primo $p$ y $\gcd(a, p) = 1$: $$a^k \equiv a^{k \mod (p-1)} \pmod{p}$$

Demostración

Demostración 1: Argumento de Conteo

Considera el conjunto $S = {a, 2a, 3a, \ldots, (p-1)a}$ reducido módulo $p$.

Afirmación: $S \equiv {1, 2, 3, \ldots, p-1} \pmod{p}$ (vistos como conjuntos).

Prueba de la afirmación:

• Cada elemento de $S$ es distinto de cero módulo $p$ (porque $\gcd(a, p) = 1$).
• Los elementos son todos diferentes: si $ia \equiv ja \pmod{p}$ para $1 \leq i < j \leq p-1$, entonces $(j-i)a \equiv 0 \pmod{p}$, lo cual es imposible porque $\gcd(a, p) = 1$ y $0 < j - i < p$.
• Como $S$ tiene $p-1$ residuos distintos y no nulos módulo $p$, tiene que ser igual al conjunto ${1, 2, \ldots, p-1}$.

Ahora, multiplica todos los elementos: $$a \cdot 2a \cdot 3a \cdots (p-1)a \equiv 1 \cdot 2 \cdot 3 \cdots (p-1) \pmod{p}$$ $$a^{p-1} \cdot (p-1)! \equiv (p-1)! \pmod{p}$$

Como $\gcd((p-1)!, p) = 1$, puedes dividir ambos lados entre $(p-1)!$: $$a^{p-1} \equiv 1 \pmod{p}$$ $\square$

Demostración 2: Inducción

La idea es probar que $a^p \equiv a \pmod{p}$ para todos los enteros $a \geq 0$.

Caso base: $0^p = 0 \equiv 0 \pmod{p}$. $\checkmark$

Paso inductivo: Supón que $a^p \equiv a \pmod{p}$. Lo que hay que probar es que $(a+1)^p \equiv a+1 \pmod{p}$.

Si usas el teorema del binomio: $$(a+1)^p = \sum_{k=0}^{p} \binom{p}{k} a^k = a^p + \binom{p}{1}a^{p-1} + \cdots + \binom{p}{p-1}a + 1$$

Para $0 < k < p$, tienes que $\binom{p}{k} = \frac{p!}{k!(p-k)!}$.

Como $p$ es primo, $p$ divide al numerador pero no al denominador, así que $p \mid \binom{p}{k}$.

Por lo tanto: $$(a+1)^p \equiv a^p + 1 \equiv a + 1 \pmod{p}$$ $\square$

Demostración 3: Teoría de Grupos

El grupo multiplicativo $(\mathbb{Z}/p\mathbb{Z})^*$ tiene orden $p - 1$.

Por el teorema de Lagrange, para cualquier elemento $a$ en este grupo: $$a^{|G|} = a^{p-1} = 1$$

y eso significa que $a^{p-1} \equiv 1 \pmod{p}$. $\square$