Pequeño Teorema de Fermat

Módulo 5 · Teoría de Números

Un atajo para exponentes gigantes

Cuando pagas en línea o abres un chat cifrado, el computador hace cuentas con potencias enormes módulo un número. La criptografía RSA se apoya en una generalización del teorema de esta lección, que Pierre de Fermat enunció en 1640. Antes de la fórmula, mira qué hacen las potencias de 3 en un reloj de 7.

Momento animado

Las potencias de 3 en un reloj de 7

Cada salto multiplica por 3 y se queda con el residuo módulo 7. Cuenta los saltos hasta volver a 1.

Potenciaexponente 0

Etapas

Etapa 1 de 4 · 3⁰

Un reloj de 7 posiciones (los residuos módulo 7) y potencias de 3. Empezamos en 3⁰ = 1; cada salto multiplica por 3.

El Pequeño Teorema de Fermat

Teorema (Fermat, 1640)

Si $p$ es primo y $\gcd(a, p) = 1$ , entonces:

a^{p-1} \equiv 1 \pmod{p}

Equivalentemente: $a^p \equiv a \pmod{p}$ para todo entero $a$ .

¿Por qué es revolucionario? Porque permite reducir exponentes gigantescos:

Ejemplo: Calcular 2¹⁰⁰⁰ mod 13

Fermat: 13 es primo, gcd(2,13) = 1

2^{12} \equiv 1 \pmod{13}

Reducir exponente: 1000 = 12 × 83 + 4

2^{1000} = (2^{12})^{83} \cdot 2^4

Aplicar Fermat

\equiv 1^{83} \cdot 16 \equiv 3 \pmod{13}

Concepto Clave

"Si p es primo y p no divide a 'a', reduce el exponente módulo (p-1). Eso es todo."

Demostración y Comprensión Profunda

La demostración clásica usa el argumento de los residuos:

1. Consideremos los números $a, 2a, 3a, \ldots, (p-1)a$ .

2. Ninguno es $\equiv 0 \pmod{p}$ (pues $\gcd(a,p)=1$ ).

3. Son todos distintos mod $p$ : si $ia \equiv ja \pmod{p}$ con $1 \leq i < j \leq p-1$ , al cancelar $a$ (válido pues $\gcd(a,p)=1$ ) se tendría $i \equiv j$ , contradicción.

4. Son una permutación de $\{1, 2, \ldots, p-1\}$ mod $p$ .

5. Multiplicar todos:

a \cdot 2a \cdots (p-1)a \equiv 1 \cdot 2 \cdots (p-1) \pmod{p}

6. Factorizar: $a^{p-1} \cdot (p-1)! \equiv (p-1)! \pmod{p}$

7. Cancelar $(p-1)!$ (es coprimo con $p$ ). Resultado: $a^{p-1} \equiv 1$ . ∎

✓ Puedes usar Fermat cuando...

• El módulo es primo
• La base NO es múltiplo del módulo
• Necesitas simplificar $a^n \bmod p$

✗ NO funciona cuando...

• El módulo es compuesto (usa Euler)
• $p \mid a$ (el resultado es trivial: 0)

Concepto Clave

"La demostración de Fermat es un argumento de CONTEO: multiplicar por 'a' solo permuta los residuos, no crea nuevos."

Problemas de Olimpiada

Residuo de potencia con Fermat

Encuentre el residuo de $3^{100}$ al dividir entre 7:

Divisibilidad clásica por 42

Demuestre que $n^7 - n$ es divisible por 42 para todo entero $n$ :

Práctica · Fermat con p = 7

¿Cuál es el residuo de

3^6

al dividir entre 7?

Práctica · Reducir el exponente

¿Cuál es el residuo de

2^{100}

al dividir entre 7?

Argumentación · ¿Cuándo vale?

Alguien dice: «por Fermat,

2^8 \equiv 1 \pmod 9

». ¿Tiene razón?