Teorema de Wilson: (p − 1)! ≡ −1 (mod p) para los números primos

Actualizado el
El teorema de Wilson dice que un número p mayor que 1 es primo exactamente cuando (p − 1)! + 1 es múltiplo de p. Por ejemplo, 4! + 1 = 25 es múltiplo de 5, y 5 es primo. Caracteriza los números primos, aunque no sirve para buscarlos en la práctica; su utilidad real está en calcular restos de factoriales grandes.
Enunciado
Para todo entero p > 1:
p es primo ⟺ (p − 1)! ≡ −1 (mod p)
La congruencia significa que (p − 1)! deja resto p − 1 al dividir entre p o, lo que es lo mismo, que p divide a (p − 1)! + 1. El teorema tiene dos partes: si p es primo, se cumple la congruencia (la parte difícil), y si se cumple la congruencia, p es primo (el recíproco, que es fácil).
Comprobación con números pequeños
| n | (n − 1)! | (n − 1)! mod n | ¿Primo? |
|---|---|---|---|
| 2 | 1 | 1 (= −1 mod 2) | Sí |
| 3 | 2 | 2 (= −1) | Sí |
| 4 | 6 | 2 | No |
| 5 | 24 | 4 (= −1) | Sí |
| 6 | 120 | 0 | No |
| 7 | 720 | 6 (= −1) | Sí |
| 11 | 3 628 800 | 10 (= −1) | Sí |
| 12 | 39 916 800 | 0 | No |
Para n = 7: 720 + 1 = 721 = 7 · 103. Comprobando con un ordenador todos los n de 2 a 39, la congruencia se cumple exactamente para 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 y 37, que son los primos de ese rango.
Demostración
Si p es primo, (p − 1)! ≡ −1 (mod p)
Para p = 2 y p = 3 se comprueba directamente (1! = 1 ≡ −1 mod 2 y 2! = 2 ≡ −1 mod 3). Sea p ≥ 5 primo.
- Como p es primo, cada número a de {1, 2, …, p − 1} tiene un inverso módulo p: un único b del mismo conjunto con a·b ≡ 1 (mod p). Es una consecuencia de la identidad de Bézout, porque mcd(a, p) = 1.
- ¿Qué números son su propio inverso? Los que cumplen a2 ≡ 1, es decir, p divide a (a − 1)(a + 1). Como p es primo, divide a uno de los dos factores, y eso solo pasa con a = 1 o a = p − 1.
- Los demás números, de 2 a p − 2, se agrupan en parejas {a, b} con a·b ≡ 1, distintas entre sí. Al multiplicarlos todos, cada pareja aporta un factor 1: 2 · 3 · … · (p − 2) ≡ 1 (mod p).
- Por tanto, (p − 1)! = 1 · [2 · … · (p − 2)] · (p − 1) ≡ 1 · 1 · (p − 1) ≡ −1 (mod p).
Ejemplo con p = 11: las parejas son {2, 6}, {3, 4}, {5, 9} y {7, 8}, porque 2·6 = 12, 3·4 = 12, 5·9 = 45 y 7·8 = 56, y todos dejan resto 1 al dividir entre 11. Así 10! ≡ 1 · 1 · 1 · 1 · 1 · 10 ≡ 10 ≡ −1 (mod 11).
Si n es compuesto, la congruencia falla
Si n = a·b con 1 < a < n, el factor a aparece en (n − 1)!, así que a divide a (n − 1)!. Si además n dividiera a (n − 1)! + 1, también a lo dividiría, y entonces a dividiría a la diferencia, que es 1. Imposible. Más aún: para todo compuesto n > 4 se cumple (n − 1)! ≡ 0 (mod n); el único compuesto con resto distinto de cero es 4, con 3! = 6 ≡ 2 (mod 4).
Para qué sirve: restos de factoriales grandes
Ejemplo 1: 15! módulo 17
Por Wilson, 16! ≡ −1 (mod 17). Como 16! = 16 · 15! y 16 ≡ −1 (mod 17), queda (−1) · 15! ≡ −1, así que 15! ≡ 1 (mod 17). En general, (p − 2)! ≡ 1 (mod p) para todo primo p.
Ejemplo 2: 97! módulo 101
101 es primo, así que 100! ≡ −1 (mod 101). Además 100! = 100 · 99 · 98 · 97! y, módulo 101, 100 ≡ −1, 99 ≡ −2 y 98 ≡ −3. Su producto es (−1)(−2)(−3) = −6. Entonces −6 · 97! ≡ −1, es decir, 6 · 97! ≡ 1 (mod 101). El inverso de 6 módulo 101 es 17, porque 6 · 17 = 102 ≡ 1. Resultado: 97! ≡ 17 (mod 101), comprobado también por cálculo directo.
Ejemplo 3: un resto que parece imposible a mano
¿Qué resto deja 12! al dividir entre 13? Directamente por Wilson: 12 (es decir, −1). El número 12! = 479 001 600 no hace falta calcularlo.
Por qué no se usa para buscar primos
Comprobar si n es primo con el teorema exige calcular (n − 1)! módulo n, lo que supone unas n multiplicaciones. Para un número de 20 cifras eso es inabarcable, mientras que las pruebas de primalidad que se usan en la práctica, como las basadas en el pequeño teorema de Fermat, necesitan un número de operaciones que crece con el número de cifras, no con el tamaño del número. El valor del teorema de Wilson es teórico y de cálculo de restos, no de búsqueda.
Errores habituales
- Usar p! en vez de (p − 1)!. p! siempre es múltiplo de p, así que p! ≡ 0.
- Olvidar que −1 ≡ p − 1. Si la calculadora da 4 para 4! mod 5, eso es −1.
- Aplicarlo a módulos compuestos. 5! mod 6 = 0, no −1. Wilson solo vale con módulo primo.
- Confundirlo con Fermat. El pequeño teorema de Fermat habla de potencias (ap−1 ≡ 1), Wilson de factoriales.
Historia
El matemático Ibn al-Haytham ya enunció el resultado hacia el año 1000. Hay indicios de que Leibniz lo conocía, aunque no lo publicó. Edward Waring lo anunció en 1770 en sus Meditationes Algebraicae, sin demostración, atribuyéndolo a su alumno John Wilson, y Joseph-Louis Lagrange publicó la primera demostración en 1771.
Relación con otros teoremas y curiosidades
La demostración usa la misma idea que el teorema de Euler de la aritmética modular: los restos invertibles módulo n forman un grupo con el producto. Desde el punto de vista del álgebra, el teorema dice que el producto de todos los elementos del grupo de unidades módulo p es −1, que es el único elemento de orden 2. También se puede deducir de que el polinomio xp−1 − 1 tiene como raíces, módulo p, los números 1, 2, …, p − 1 (por Fermat) y se factoriza como (x − 1)(x − 2)···(x − (p − 1)); igualando los términos independientes sale Wilson. Esa factorización a partir de las raíces es la misma idea del teorema del factor, aplicada ahora a restos módulo p. Y el número de raíces de un polinomio, que en ℂ fija el teorema fundamental del álgebra, módulo p está acotado por su grado.
Los primos de Wilson son los primos p tales que p2 (y no solo p) divide a (p − 1)! + 1. Solo se conocen tres: 5, 13 y 563. Se ha comprobado que no hay otros por debajo de 2·1013.
Preguntas frecuentes
¿Qué dice el teorema de Wilson?
Que un entero p > 1 es primo si y solo si (p − 1)! + 1 es múltiplo de p, es decir, (p − 1)! ≡ −1 (mod p).
¿Se cumple el teorema de Wilson para números compuestos?
No. Para todo compuesto n > 4, (n − 1)! es múltiplo de n y deja resto 0; para n = 4 deja resto 2.
¿Quién demostró el teorema de Wilson?
Lo anunció Edward Waring en 1770 atribuyéndolo a John Wilson, y la primera demostración publicada es de Lagrange, en 1771. Ibn al-Haytham lo había enunciado hacia el año 1000.
¿Para qué sirve en los ejercicios?
Para calcular restos de factoriales grandes módulo un primo. Por ejemplo, 15! ≡ 1 (mod 17) y 97! ≡ 17 (mod 101).
RELACIONADOS