Teorema de Wilson

En álgebra y teoría de números , el teorema de Wilson establece que un número natural n > 1 es un número primo si y solo si el producto de todos los enteros positivos menores que n es uno menos que un múltiplo de n . Es decir (usando las notaciones de la aritmética modular ), el factorial satisface${\displaystyle (n-1)!=1\times 2\times 3\times \cdots \times (n-1)}$

${\displaystyle (n-1)!\ \equiv \;-1{\pmod {n}}}$

exactamente cuando n es un número primo. En otras palabras, cualquier entero n > 1 es un número primo si, y sólo si, ( n  − 1)! + 1 es divisible por n . ^[1]

El teorema fue enunciado por primera vez por Ibn al-Haytham alrededor del año  1000 d . C. ^[2] Edward Waring anunció el teorema en 1770 sin demostrarlo, atribuyendo el descubrimiento a su alumno John Wilson . ^[3] Lagrange dio la primera prueba en 1771. ^[4] Hay evidencia de que Leibniz también conocía el resultado un siglo antes, pero nunca lo publicó. ^[5]

Para cada uno de los valores de n desde 2 hasta 30, la siguiente tabla muestra el número ( n  − 1)! y el resto cuando ( n  − 1)! se divide por n . (En la notación de aritmética modular , el resto cuando m se divide por n se escribe m mod n .) El color de fondo es azul para valores primos de n y dorado para valores compuestos .

Tabla de factoriales y su resto módulo n

${\estilo de visualización n}$	${\estilo de visualización (n-1)!}$ (secuencia A000142 en la OEIS )	${\displaystyle (n-1)!\ {\bmod {\ }}n}$ (secuencia A061006 en la OEIS )
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

Como enunciado bicondicional (si y solo si), la prueba tiene dos mitades: mostrar que la igualdad no se cumple cuando es compuesto, y mostrar que sí se cumple cuando es primo.${\estilo de visualización n}$${\estilo de visualización n}$

Supóngase que es compuesto. Por lo tanto, es divisible por algún número primo donde . Como divide a , existe un entero tal que . Supóngase por contradicción que fueran congruentes con módulo . Entonces también serían congruentes con módulo : en efecto, si entonces para algún entero , y en consecuencia es uno menos que un múltiplo de . Por otra parte, como , uno de los factores del producto desarrollado es . Por lo tanto . Esto es una contradicción; por lo tanto, no es posible que cuando sea compuesto.${\estilo de visualización n}$${\estilo de visualización q}$${\displaystyle 2\leq q<n}$${\estilo de visualización q}$${\estilo de visualización n}$${\estilo de visualización k}$${\estilo de visualización n=qk}$${\estilo de visualización (n-1)!}$${\estilo de visualización -1}$${\estilo de visualización {n}}$${\estilo de visualización (n-1)!}$${\estilo de visualización -1}$${\estilo de visualización {q}}$${\displaystyle (n-1)!\equiv -1{\pmod {n}}}$${\displaystyle (n-1)!=nm-1=(qk)m-1=q(km)-1}$${\estilo de visualización m}$${\estilo de visualización (n-1)!}$${\estilo de visualización q}$${\displaystyle 2\leq q\leq n-1}$${\displaystyle (n-1)!=(n-1)\times (n-2)\times \cdots \times 2\times 1}$${\estilo de visualización q}$${\displaystyle (n-1)!\equiv 0{\pmod {q}}}$${\displaystyle (n-1)!\equiv -1{\pmod {n}}}$${\estilo de visualización n}$

De hecho, es cierto que hay más. Con la única excepción del caso , donde , si es compuesto, entonces es congruente con 0 módulo . La prueba se puede dividir en dos casos: primero, si se puede factorizar como el producto de dos números desiguales, , donde , entonces tanto y aparecerán como factores en el producto y, por lo tanto, es divisible por . Si no tiene tal factorización, entonces debe ser el cuadrado de algún primo mayor que 2. Pero entonces , por lo que tanto y serán factores de , y, por lo tanto, divide también en este caso.${\estilo de visualización n=4}$${\displaystyle 3!=6\equiv 2{\pmod {4}}}$${\estilo de visualización n}$${\estilo de visualización (n-1)!}$${\estilo de visualización n}$${\estilo de visualización n}$${\estilo de visualización n=ab}$${\displaystyle 2\leq a<b<n}$${\estilo de visualización a}$${\estilo de visualización b}$${\displaystyle (n-1)!=(n-1)\times (n-2)\times \cdots \times 2\times 1}$${\estilo de visualización (n-1)!}$${\displaystyle ab=n}$${\estilo de visualización n}$${\estilo de visualización q}$${\displaystyle 2q<q^{2}=n}$${\estilo de visualización q}$${\estilo de visualización 2q}$${\estilo de visualización (n-1)!}$${\estilo de visualización n}$${\estilo de visualización (n-1)!}$

Las dos primeras pruebas a continuación utilizan el hecho de que las clases de residuos módulo un número primo son un cuerpo finito (consulte el artículo Cuerpo primo para obtener más detalles). ^[6]

El resultado es trivial cuando , por lo que se supone que es un primo impar, . Dado que las clases de residuos módulo forman un cuerpo, cada residuo distinto de cero tiene un inverso multiplicativo único . El lema de Euclides implica ^[a] que los únicos valores de para los cuales son . Por lo tanto, con la excepción de , los factores en la forma desarrollada de se pueden organizar en pares disjuntos de modo que el producto de cada par sea congruente con 1 módulo . Esto demuestra el teorema de Wilson.${\estilo de visualización p=2}$${\estilo de visualización p}$${\displaystyle p\geq 3}$${\estilo de visualización p}$${\estilo de visualización a}$$estilo de visualización a^{-1}}$${\estilo de visualización a}$${\displaystyle a\equiv a^{-1}{\pmod {p}}}$${\displaystyle a\equiv \pm 1{\pmod {p}}}$${\estilo de visualización \pm 1}$${\estilo de visualización (p-1)!}$${\estilo de visualización p}$

Por ejemplo, para , se tiene${\displaystyle p=11}$$${\displaystyle 10!=[(1\cdot 10)]\cdot [(2\cdot 6)(3\cdot 4)(5\cdot 9)(7\cdot 8)]\equiv [-1]\cdot [1\cdot 1\cdot 1\cdot 1]\equiv -1{\pmod {11}}.}$$

Nuevamente, el resultado es trivial para p  = 2, por lo que supongamos que p es un primo impar, p ≥ 3. Considere el polinomio

${\displaystyle g(x)=(x-1)(x-2)\cdots (x-(p-1)).}$

g tiene grado p − 1 , término principal x ^{p − 1} y término constante ( p − 1)! . Sus raíces p − 1 son 1, 2, ..., p − 1 .

Ahora consideremos

${\displaystyle h(x)=x^{p-1}-1.}$

h también tiene grado p − 1 y término principal x ^{p − 1} . Módulo p , el pequeño teorema de Fermat dice que también tiene las mismas raíces p − 1 , 1, 2, ..., p − 1 .

Por último, considere

${\displaystyle f(x)=g(x)-h(x).}$

f tiene grado como máximo p  − 2 (ya que los términos principales se cancelan), y módulo p también tiene las raíces p − 1 1, 2, ..., p − 1 . Pero el teorema de Lagrange dice que no puede tener más de p  − 2 raíces. Por lo tanto, f debe ser idénticamente cero (mod p ), por lo que su término constante es ( p − 1)! + 1 ≡ 0 (mod p ) . Este es el teorema de Wilson.

Es posible deducir el teorema de Wilson a partir de una aplicación particular de los teoremas de Sylow . Sea p un primo. Es inmediato deducir que el grupo simétrico tiene exactamente elementos de orden p , es decir, los p -ciclos . Por otra parte, cada p -subgrupo de Sylow en es una copia de . Por lo tanto, se sigue que el número de p -subgrupos de Sylow es . El tercer teorema de Sylow implica${\displaystyle S_{p}}$${\displaystyle (p-1)!}$${\displaystyle C_{p}}$${\displaystyle S_{p}}$${\displaystyle C_{p}}$${\displaystyle n_{p}=(p-2)!}$

${\displaystyle (p-2)!\equiv 1{\pmod {p}}.}$

Multiplicando ambos lados por ( p − 1) obtenemos

${\displaystyle (p-1)!\equiv p-1\equiv -1{\pmod {p}},}$

es decir, el resultado.

En la práctica, el teorema de Wilson es inútil como prueba de primalidad porque calcular ( n − 1)! módulo n para n grande es computacionalmente complejo , y se conocen pruebas de primalidad mucho más rápidas (de hecho, incluso la división por tanteo es considerablemente más eficiente). ^{[ cita requerida ]}

Si se utiliza en sentido inverso, para determinar la primalidad de los sucesores de grandes factoriales, es un método muy rápido y eficaz, pero de utilidad limitada. ^{[ cita requerida ]}

Usando el Teorema de Wilson, para cualquier primo impar p = 2 m + 1 , podemos reordenar el lado izquierdo de para obtener la igualdad Esto se convierte en o Podemos usar este hecho para probar parte de un resultado famoso: para cualquier primo p tal que p  ≡ 1 (mod 4) , el número (−1) es un cuadrado ( residuo cuadrático ) mod p . Para esto, supongamos p  = 4 k  + 1 para algún entero k . Luego podemos tomar m  = 2 k anterior, y concluimos que ( m !) ² es congruente con (−1) (mod p ).$${\displaystyle 1\cdot 2\cdots (p-1)\ \equiv \ -1\ {\pmod {p}}}$$$${\displaystyle 1\cdot (p-1)\cdot 2\cdot (p-2)\cdots m\cdot (p-m)\ \equiv \ 1\cdot (-1)\cdot 2\cdot (-2)\cdots m\cdot (-m)\ \equiv \ -1{\pmod {p}}.}$$$${\displaystyle \prod _{j=1}^{m}\ j^{2}\ \equiv (-1)^{m+1}{\pmod {p}}}$$$${\displaystyle (m!)^{2}\equiv (-1)^{m+1}{\pmod {p}}.}$$

El teorema de Wilson se ha utilizado para construir fórmulas para números primos , pero son demasiado lentas para tener valor práctico.

El teorema de Wilson permite definir la función gamma p-ádica .

Gauss demostró ^{[7] [ se necesita una fuente no primaria ]} que donde p representa un primo impar y un entero positivo. Es decir, el producto de los enteros positivos menores que m y primos relativos a m es uno menos que un múltiplo de m cuando m es igual a 4, o una potencia de un primo impar, o dos veces una potencia de un primo impar; en caso contrario, el producto es uno más que un múltiplo de m . Los valores de m para los que el producto es −1 son precisamente aquellos en los que hay una raíz primitiva módulo m .$${\displaystyle \prod _{k=1 \atop \gcd(k,m)=1}^{m}\!\!k\ \equiv {\begin{cases}-1{\pmod {m}}&{\text{if }}m=4,\;p^{\alpha },\;2p^{\alpha }\\\;\;\,1{\pmod {m}}&{\text{otherwise}}\end{cases}}}$$${\displaystyle \alpha }$

• Wilson primo
• Tabla de congruencias
• Conjetura de Agoh-Giuga

• "Teorema de Wilson", Enciclopedia de Matemáticas , EMS Press , 2001 [1994]
• Weisstein, Eric W. "Teorema de Wilson". MathWorld .
• Prueba del sistema Mizar : http://mizar.org/version/current/html/nat_5.html#T22
• Ohana, Andrew. "Una generalización del teorema de Wilson" (PDF) .