Pequeño Teorema de Fermat

Modulo 5 · Teoría de Números

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^1000 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

Problema 1

Residuo de potencia

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

Ver Solución

Por Fermat: $3^6 \equiv 1 \pmod{7}$

$100 = 6 \times 16 + 4$

$3^{100} = (3^6)^{16} \cdot 3^4 \equiv 1 \cdot 81 \equiv 81 \bmod 7$

81 = 7 \times 11 + 4

. Residuo: 4.

Problema 2 — IMO

Divisibilidad clásica

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

Ver Solución

$42 = 2 \times 3 \times 7$ . Basta probar divisibilidad por 2, 3, y 7.

Mod 2: $n^7 \equiv n \pmod{2}$ (Fermat con p=2). ✓

Mod 3: $n^3 \equiv n \pmod{3}$ → $n^7 = (n^3)^2 \cdot n \equiv n^2 \cdot n = n^3 \equiv n$ . ✓

Mod 7: $n^7 \equiv n \pmod{7}$ (Fermat directamente). ✓

2 \mid n^7-n, \; 3 \mid n^7-n, \; 7 \mid n^7-n \implies 42 \mid n^7 - n

. ∎