Teorema de Wilson

En matemáticas, el teorema de Wilson es un teorema clásico relacionado con la divisibilidad. Se enuncia de la siguiente manera:

Si p es un número primo, entonces (p − 1)! ≡ -1 (mod p)

John Wilson

El recíproco también es cierto, por lo que puede afirmarse que un número n>1 es primo si y sólo si (n− 1)! ≡ − 1 (mod n). Sin embargo, sólo la implicación de arriba es conocida como teorema de Wilson (o Congruencia de Wilson).

Historia

Fue atribuido a John Wilson por Edward Waring, quien en 1770 realizó un comentario acerca de que Wilson había dejado anotado el resultado. No hay evidencia de que Wilson hubiese hallado la demostración, y ciertamente Waring no la halló. Fue Lagrange quien, en 1771 dio la primera demostración. Con toda propiedad, el teorema debe ser atribuido a Abu 'Ali al-Hasan ibn al-Haytham, llamado en Occidente Alhazen, quien lo formuló a comienzos del siglo XI.

Ejemplo

La siguiente tabla muestra los valores de n desde 2 a 30, (n-1)!, Y el resto al (n-1)! se divide por n. (El resto cuando m se divide por n se escribe m mod n). El color de fondo es de color rosa para los valores primos de n, color verde claro para valores compuestos.

Tabla de resto módulo n
$n$	$(n-1)!$	$(n-1)!\ {\bmod {\ }}n$
2	1	1
3	2	2
4	6	2
5	24	4
6	120	0
7	720	6
8	5040	0
9	40320	0
10	362880	0
11	3628800	10
12	39916800	0
13	479001600	12
14	6227020800	0
15	87178291200	0
16	1307674368000	0
17	20922789888000	16
18	355687428096000	0
19	6402373705728000	18
20	121645100408832000	0
21	2432902008176640000	0
22	51090942171709440000	0
23	1124000727777607680000	22
24	25852016738884976640000	0
25	620448401733239439360000	0
26	15511210043330985984000000	0
27	403291461126605635584000000	0
28	10888869450418352160768000000	0
29	304888344611713860501504000000	28
30	8841761993739701954543616000000	0

Demostración

Usando aritmética modular

De derecha a izquierda

Por contradicción. Suponga que $p\geq 2,(p-1)!\equiv (p-1)\ {\mbox{mod}}\ p\,$ y $p\,$ no es primo. Dado que $p\,$ no es primo, existe $a\in \{1,\ldots ,p-1\}.\,$ tal que $a\,|\,p\,$ , es decir, ${\mbox{MCD}}\ (a,p)\neq 1$ . Además, no es difícil ver que $(p-1)!=a\cdot (a-1)!\cdot \prod _{i=a+1}^{p-1}i.\,$ . Si escribimos $\alpha =(a-1)!\cdot \prod _{i=a+1}^{p-1}i.\,$ entonces, a partir de la hipótesis se concluye que $a\cdot \alpha \equiv (p-1)\ {\mbox{mod}}\ p.\,$

Además, aprovechando el hecho de que $(p-1)\equiv -1\ {\mbox{mod}}\ p\,$ se deduce que $(p-1)^{2}\equiv 1\ {\mbox{mod}}\ p\,$ y luego $(a\cdot \alpha )^{2}\equiv (p-1)^{2}\equiv 1\ {\mbox{mod}}\ p.\,$ Vemos que $\ a^{2}\,$ tiene inverso en módulo $\ p\,$ , lo cual no puede ser cierto pues ${\mbox{MCD}}\ (a^{2},p)\neq 1.\,$ Esta contradicción proviene de suponer que $p\,$ no es primo.

De izquierda a derecha

Sea $p\geq 2$ un número primo. Dado que $p$ es primo, entonces para todo $a\in \{1,\ldots ,p-1\}$ se tiene que ${\mbox{MCD}}\ (a,p)=1\,$ y entonces cada $a\in \{1,\ldots ,p-1\}$ tiene un único inverso módulo $p\,$ en el conjunto $a\in \{1,\ldots ,p-1\}$ .

Para ver que es único, supongamos $b,c\in \{1,\ldots ,p-1\}$ tales que $b>c,a\cdot b\equiv \ 1\ {\mbox{mod}}\ p$ y $a\cdot c\equiv \ 1\ {\mbox{mod}}\ p$ . Luego se tiene $a\cdot b\cdot c\equiv \ c\ {\mbox{mod}}\ p$ , de donde $b\equiv \ c\ {\mbox{mod}}\ p.$

De lo anterior se colige que $p\,|\,(b-c).$ Además, del supuesto se tiene que $(b-c)\in \{1,\ldots ,p-1\}.$ Sin embargo, para cada $a\in \{1,\ldots ,p-1\}$ se tiene que ${\mbox{MCD}}\ (a,p)=1\,$ , es decir, $p\not |(b-c).$ , lo cual es una contradicción. Lo mismo ocurre si $c>b.\,$ Vemos entonces que $b=c$ , lo que garantiza la unicidad.

Ahora, es claro que $1,(p-1)$ son inversos de sí mismos en módulo $p$ , y para todo otro elemento en $\{1,\ldots ,p-1\}$ se tiene un inverso en módulo $p$ diferente al de los demás (por la unicidad). Así, podemos agrupar cada elemento con su inverso, de modo que $\prod _{i=2}^{p-2}i\equiv \ 1\ {\mbox{mod}}\ p.$

De aquí, multiplicando a ambos lados por $(p-1)$ se concluye $(p-1)!\equiv \ (p-1)\ {\mbox{mod}}\ p$ , lo que finaliza la demostración.

Usando teoría de grupos

Esta demostración usa el hecho de que si p es un número primo, entonces el conjunto de números G = (Z/pZ)^× = {1, 2, ... p − 1} forma un grupo bajo la multiplicación. Esto significa que para cada elemento a de G, hay un único inverso multiplicativo b en G tal que ab ≡ 1 (mod p). Si a ≡ b (mod p), entonces a² ≡ 1 (mod p), que se puede factorizar en a² − 1 = (a + 1)(a − 1) ≡ 0 (mod p), y puesto que p es primo, entonces a ≡ 1 o −1 (mod p), por ejemplo a = 1 o a = p − 1.

En otras palabras, 1 y p − 1 son cada uno su propio inverso, pero para cualquier otro elemento de G hay un inverso, también en G, así que si tomamos todos los elementos de G por parejas y los multiplicamos todos ellos juntos, el producto será igual a −1 (módulo p). Por ejemplo, si p = 11, tenemos que:

10!=1(10)(2\cdot 6)(3\cdot 4)(5\cdot 9)(7\cdot 8)\ \equiv \ -1\ ({\mbox{mod}}\ 11).\,

Las propiedades conmutativas y asociativas son usadas en el procedimiento de arriba. Todos los elementos en el producto anterior serán de la forma g g ⁻¹ ≡ 1 (mod p) excepto 1 (p − 1), que están al principio del producto.

Si p = 2, el resultado es trivial e inmediato.

Para demostrar el inverso del teorema (ver siguiente sección), supóngase que la congruencia se cumple para un número compuesto n, nótese entonces que n tiene un divisor propio d con 1 < d < n. Claramente, d divide a (n − 1)! pero por la congruencia, d también divide a (n − 1)! + 1, así que d divide a 1, con lo que se llega a una contradicción.

Usando polinomios

Sea p un número primo. Consideremos el polinomio

g(x)=(x-1)(x-2)\cdots (x-(p-1)).\,

Recordemos que si f(x) es un polinomio no nulo de grado d sobre un cuerpo F, entonces f(x) tiene un máximo de d raíces en F, y recordemos que el conjunto de todos los restos módulo un primo, con las operaciones de suma y multiplicación, es un cuerpo. Ahora, siendo g(x)

f(x)=g(x)-(x^{p-1}-1).\,

Puesto que los coeficientes de mayor orden se cancelan, f(x) es un polinomio de grado p − 2 como mucho. Por tanto, si tomamos restos módulo p, f(x) tendrá a lo sumo p − 2 raíces módulo p. Sin embargo, a la vista de la definición de f(x), del pequeño teorema de Fermat se sigue que cada elemento 1, 2, ..., p − 1 es una raíz de f(x) (por lo que, a fortiori, es una raíz de f(x) módulo p). Esto es imposible a menos que f(x) sea idénticamente cero módulo p, esto es, a menos que cada coeficiente de f(x) sea divisible por p.

Dado que el término constante de f(x) es justamente (p − 1)! + 1,

Inverso

El inverso del teorema de Wilson dice que para cualquier número compuesto n > 5,

n divide a (n − 1)!.

Se deja el caso n = 4, para el cual 3! no es divisible por 4 (es únicamente divisible por 2).

En efecto, si q es un factor primo de n, de tal manera que n = qa, los números

1, 2, ..., n − 1

incluyendo a − 1 múltiplos de q. Por lo tanto, las potencias de q que dividen al factorial son al menos n/q − 1; y las potencias que dividen a n son a lo máximo

log n/log q.

La inecuación

log n/log q ≤ n/q − 1

se cumple en general, excepto para el caso q = 2 y n = 4.

Test de primalidad

El teorema de Wilson no se utiliza como test de primalidad en la práctica, ya que para calcular (n − 1)! modulo n para un número n grande es costoso (computacionalmente hablando), y se conocen tests más sencillos y rápidos.

Usando el teorema del Wilson, se tiene que para cada número primo p:

1\cdot 2\cdots (p-1)\ \equiv \ -1\ ({\mbox{mod}}\ p)

1\cdot (p-1)\cdot 2\cdot (p-2)\cdots n\cdot (p-n)\ \equiv \ 1\cdot (-1)\cdot 2\cdot (-2)\cdots n\cdot (-n)\ \equiv \ -1\ ({\mbox{mod}}\ p)

donde p = 2n + 1. Esto se convierte en

\prod _{j=1}^{n}\ j^{2}\ \equiv (-1)^{n+1}\ ({\mbox{mod}}\ p).

Así, la primalidad del número se determina mediante los residuos cuadráticos de p. Esto se puede usar de hecho para probar parte de otro famoso resultado: −1 es un cuadrado (residuo cuadrático) mod p si p ≡ 1 (mod 4). Para la suposición, p = 4k + 1 para algún entero k. Entonces, tomando n = 2k y sustituyendo, se concluye que:

\left(\prod _{j=1}^{2k}\ j\right)^{2}=\prod _{j=1}^{2k}\ j^{2}\ \equiv (-1)^{2k+1}\ =-1({\mbox{mod}}\ p).

El teorema de Wilson ha sido utilizado para generar fórmulas para los primos, pero es demasido lento como para tener valor práctico.

Generalización

El teorema de Wilson se puede generalizar, como mostró Carl Friedrich Gauss en su libro Disquisitiones Arithmeticae:

\prod _{1\leq a<n \atop (a,n)=1}\!\!a\ \equiv \ \left\{{\begin{matrix}-1\ ({\mbox{mod }}n)&{\mbox{si }}n=4,\;p^{k},\;2p^{k}\\\ \ 1\ ({\mbox{mod }}n)&{\mbox{en otro caso}}\end{matrix}}\right.

donde p es un número primo impar, y k pertenece a los números naturales, es decir, $k\in \left\{1,2,3,...\right\}$ . El teorema se generaliza más por el hecho de que en cualquier grupo abeliano finito, ya sea el producto de todos los elementos es la identidad, o precisamente hay un elemento a de orden 2. En este último caso, el producto de todos los elementos es igual a.

Véase también

Referencias

Eric W. Weisstein. «Wilson's theorem.». Consultado el 30 de diciembre de 2008.

Reid, Constance (2006). From Zero to Infinity: What Makes Numbers Interesting. Massachusetts (USA): AK Peters. ISBN 1568812736.