Pequeño teorema de Fermat: enunciado, demostración y ejemplos

Actualizado el
El pequeño teorema de Fermat dice que, si p es un número primo, ap − a es siempre múltiplo de p, sea cual sea el entero a. En la práctica sirve para calcular el resto de potencias gigantescas sin hacerlas, para hallar inversos en aritmética modular y como primera prueba rápida de si un número es primo. Es también la base del teorema de Euler y, a través de él, del cifrado RSA.
Enunciado
Sea p un número primo y a un entero cualquiera. Entonces
ap ≡ a (mod p)
Si además p no divide a a, se puede dividir entre a y se obtiene la forma más usada:
ap−1 ≡ 1 (mod p)
Recuerda que x ≡ y (mod p) significa que x e y dan el mismo resto al dividir entre p, o sea, que p divide a x − y. Por ejemplo, con p = 5 y a = 2: 24 = 16 = 3·5 + 1, así que 24 ≡ 1 (mod 5).
Demostración
Por inducción, con el binomio de Newton
Basta probarlo para a ≥ 0 (para negativos se usa que (−a)p = −ap si p es impar; para p = 2 es inmediato). Para a = 0 es evidente. Supongamos ap ≡ a y desarrollemos con el binomio de Newton:
(a + 1)p = ap + C(p,1)ap−1 + … + C(p,p−1)a + 1.
Cada coeficiente intermedio C(p,k) = p!/(k!(p−k)!) con 0 < k < p es múltiplo de p: el numerador tiene el factor primo p y el denominador no, porque k y p − k son menores que p. Por tanto (a + 1)p ≡ ap + 1 ≡ a + 1 (mod p), que es el caso siguiente.
Reordenando los restos
Si p no divide a a, los números a, 2a, 3a, …, (p − 1)a dan restos distintos al dividir entre p (si ia ≡ ja, p dividiría a (i − j)a, imposible si 0 < |i − j| < p) y ninguno es 0. Así que esos restos son 1, 2, …, p − 1 en otro orden. Multiplicando todos:
ap−1·(p − 1)! ≡ (p − 1)! (mod p),
y como (p − 1)! no es múltiplo de p, se puede simplificar: ap−1 ≡ 1 (mod p).
Ejemplos del teorema de Fermat
Ejemplo 1. Resto de 3100 entre 7
7 es primo y no divide a 3, así que 36 ≡ 1 (mod 7). Dividimos el exponente entre 6: 100 = 6·16 + 4. Entonces 3100 = (36)16·34 ≡ 1·81 ≡ 4 (mod 7), porque 81 = 11·7 + 4.
Resultado: el resto es 4.
Ejemplo 2. Resto de 7222 entre 11
710 ≡ 1 (mod 11). 222 = 10·22 + 2, así que 7222 ≡ 72 = 49 ≡ 5 (mod 11).
Ejemplo 3. Resto de 2100 entre 13
212 ≡ 1 (mod 13) y 100 = 12·8 + 4, luego 2100 ≡ 24 = 16 ≡ 3 (mod 13).
Ejemplo 4. Inverso modular
De ap−1 ≡ 1 se deduce a·ap−2 ≡ 1, así que ap−2 es el inverso de a módulo p. Inverso de 3 módulo 11: 39 = 19 683 ≡ 4 (mod 11). Comprobación: 3·4 = 12 ≡ 1 (mod 11).
Ejemplo 5. Detectar que un número es compuesto
¿Es primo 15? Si lo fuera, 214 ≡ 1 (mod 15). Pero 214 = 16 384 ≡ 4 (mod 15). Así que 15 no es primo, y lo sabemos sin buscar sus divisores. Esta es la idea del test de Fermat.
Ejemplo 6. El periodo de 1/7
Como 106 ≡ 1 (mod 7), 999 999 es múltiplo de 7 y la expresión decimal de 1/7 = 0,142857142857… se repite cada 6 cifras. En general, el periodo de 1/p (con p primo distinto de 2 y 5) divide a p − 1.
Ejemplo 7. Una divisibilidad para todos los enteros
Enunciado. Demuestra que n5 − n es múltiplo de 30 para todo entero n.
Planteamiento. 30 = 2·3·5, con los tres factores primos y distintos, así que basta ver que n5 − n es múltiplo de 2, de 3 y de 5.
- Módulo 5: es directamente el teorema con p = 5, n5 ≡ n.
- Módulo 3: n3 ≡ n, luego n5 = n3·n2 ≡ n·n2 = n3 ≡ n.
- Módulo 2: n2 ≡ n, y repitiendo, n5 ≡ n.
Resultado. Al ser múltiplo de 2, 3 y 5, lo es de 30. Comprobación con n = 7: 75 − 7 = 16 800 = 30·560.
El recíproco es falso
Que an−1 ≡ 1 (mod n) no garantiza que n sea primo:
- 2340 ≡ 1 (mod 341), y sin embargo 341 = 11·31. Se dice que 341 es un pseudoprimo en base 2.
- Hay números compuestos que pasan la prueba para toda base a sin factores comunes con ellos: los números de Carmichael. El menor es 561 = 3·11·17; por ejemplo, 2560, 5560 y 7560 dan resto 1 al dividir entre 561. Con a = 3, que sí comparte un factor, 3560 ≡ 375, y la prueba lo descubre.
Por eso el test de Fermat solo sirve para demostrar que un número es compuesto; los programas usan versiones reforzadas, como la de Miller-Rabin.
Generalización: teorema de Euler
Si n es cualquier entero positivo y a es primo con n, entonces aφ(n) ≡ 1 (mod n), donde φ(n) cuenta los números entre 1 y n primos con n. Para n = p primo, φ(p) = p − 1 y se recupera Fermat. Está explicado en la guía del teorema de Euler de la aritmética modular. Ese resultado es el que hace funcionar el cifrado RSA: al elevar el mensaje cifrado a la clave privada se recupera el original porque el producto de las dos claves es 1 más un múltiplo de φ(n).
No confundir: números y primos de Fermat
Los números de Fermat son Fn = 22n + 1. Fermat pensaba que todos eran primos; los cinco primeros (3, 5, 17, 257 y 65 537) lo son, pero Euler mostró en 1732 que F5 = 4 294 967 297 = 641·6 700 417. No se conoce ningún otro primo de Fermat. Tampoco hay que confundir este teorema con el último teorema de Fermat (xⁿ + yⁿ = zⁿ), ni el cálculo de restos de potencias con el teorema del resto de polinomios.
Historia
Fermat enunció el resultado sin demostración en una carta a Frénicle de Bessy fechada el 18 de octubre de 1640. Leibniz tenía una prueba casi igual en un manuscrito inédito anterior a 1683, y la primera demostración publicada es de Euler, en 1736. El nombre de «pequeño teorema» aparece probablemente por primera vez en 1913, en el libro Zahlentheorie de Kurt Hensel.
Preguntas frecuentes
¿Qué dice el pequeño teorema de Fermat?
Que si p es primo, aᵖ ≡ a (mod p) para todo entero a; y si p no divide a a, a^(p−1) ≡ 1 (mod p).
¿Cómo se calcula el resto de una potencia grande con Fermat?
Se divide el exponente entre p − 1 y se sustituye por su resto. Por ejemplo, 3¹⁰⁰ mod 7: 100 = 6·16 + 4, así que el resto es el de 3⁴ = 81, que es 4.
¿Si a^(n−1) ≡ 1 (mod n), n es primo?
No necesariamente. 341 = 11·31 cumple 2³⁴⁰ ≡ 1 (mod 341), y los números de Carmichael, como 561, cumplen la condición para todas las bases primas con ellos.
¿Qué diferencia hay con el teorema de Euler?
El de Euler vale para cualquier módulo n: a^φ(n) ≡ 1 (mod n) si a y n son primos entre sí. El de Fermat es el caso n primo, con φ(p) = p − 1.
RELACIONADOS