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 .

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}$${\displaystyle a^{-1}}$${\estilo de visualización a}$${\displaystyle a\equiv a^{-1}{\pmod {p}}}$${\displaystyle a\equiv \pm 1{\pmod {p}}}$${\displaystyle \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

• "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) .