El teorema de Wilson nos dice que p es un número primo, entonces
$$(p−1)! \equiv -1 (\text{mod }p)$$
El recíproco también es cierto. En efecto, supongamos tenemos un número mayor que 1, $n\in\mathbb{Z}^+$, compuesto y que verifica la igualdad anterior. Entonces por ser compuesto existen $a,b\in\mathbb{Z}^+$ tales que $n=a\,b$, siendo $1<a,b<n$. Como $(n−1)! \equiv -1 (\text{mod }n)$, implica que $(n−1)! +1=k\,n$ para cierto $k\in\mathbb{Z}$. Ahora, tanto $a$ como $b$ al ser factores de $n$ están en el producto $(n-1)!$. En consecuencia, $a$ divide a $n$ y, además, $a$ es un factor de $(n-1)!$. Luego existen $r$ y $s$ enteros tales que
$$(n−1)! +1=k\,n\Rightarrow a\,r+1=k\,s\,a\Rightarrow 1=(k\,s-r)\,a$$
Pero esto es absurdo, pues 1 no se puede factorizar con números enteros mayores que él. ¿Dónde está el error? En suponer que $n$ es compuesto.
Sabemos que el resultado lo publicó el profesor lucassiano Edwar Waring en la obra Meditationes Algebraicae (Cambridge, Inglaterra: 1770), comentando un enunciado sugerido por su alumno John Wilson:
«Hanc maxime elegantem primorum numerorum proprietatem invenit vir clarissimus, rerumque mathematicarum peritissimus Joannes Wilson Armiger.»
Sin embargo, ni Waring ni su alumno Wilson probaron el resultado, ni se dieron cuenta que el inverso también era cierto. Fue Lagrange quien probó ambas proposiciones en 1773.
El resultado es tan sencillo que apetece utilizarlo para probar si un número es primo. Pero esconde una dificultad extrema: el cálculo del factorial. La complejidad para calcular un factorial es de orden $O(n)$. Lo que significa que si en un ordenador tardamos 1 segundo en calcular 10!, emplearíamos, como máximo, 2 segundos en calcular 20!, y $n$ segundos en $n!$. Hoy las computadoras son increíblemente rápidas, y el tiempo se reduce. Aun así, cuánto tardaríamos en computar el más de un millón de cifras de 200000!.
Así que pongámonos en marcha y apliquemos nuestros conocimientos alumnos en encontrar un algoritmo que reduzca el tiempo. De partida podemos empezar con estos: The Homepage of Factorial Algorithms. Y si lo consiguen mejorarlo, siempre podremos ponerle nuestro nombre como hacía Pitágoras.
Este post participa en la Edición 8.3 del Carnaval de Matemáticas cuyo anfitrión es el Blog Semillas.