Teorema de Wilson

Teorema de los números primos

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]

Historia

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]

Ejemplo

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 .

Pruebas

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. ${\displaystyle n}$ ${\displaystyle n}$

Módulo compuesto

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. ${\displaystyle n}$ ${\displaystyle q}$ ${\displaystyle 2\leq q<n}$ ${\displaystyle q}$ ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle n=qk}$ ${\displaystyle (n-1)!}$ ${\displaystyle -1}$ ${\displaystyle {n}}$ ${\displaystyle (n-1)!}$ ${\displaystyle -1}$ ${\displaystyle {q}}$ ${\displaystyle (n-1)!\equiv -1{\pmod {n}}}$ ${\displaystyle (n-1)!=nm-1=(qk)m-1=q(km)-1}$ ${\displaystyle m}$ ${\displaystyle (n-1)!}$ ${\displaystyle q}$ ${\displaystyle 2\leq q\leq n-1}$ ${\displaystyle (n-1)!=(n-1)\times (n-2)\times \cdots \times 2\times 1}$ ${\displaystyle q}$ ${\displaystyle (n-1)!\equiv 0{\pmod {q}}}$ ${\displaystyle (n-1)!\equiv -1{\pmod {n}}}$ ${\displaystyle 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. ${\displaystyle n=4}$ ${\displaystyle 3!=6\equiv 2{\pmod {4}}}$ ${\displaystyle n}$ ${\displaystyle (n-1)!}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n=ab}$ ${\displaystyle 2\leq a<b<n}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle (n-1)!=(n-1)\times (n-2)\times \cdots \times 2\times 1}$ ${\displaystyle (n-1)!}$ ${\displaystyle ab=n}$ ${\displaystyle n}$ ${\displaystyle q}$ ${\displaystyle 2q<q^{2}=n}$ ${\displaystyle q}$ ${\displaystyle 2q}$ ${\displaystyle (n-1)!}$ ${\displaystyle n}$ ${\displaystyle (n-1)!}$

Módulo primo

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]

Prueba elemental

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. ${\displaystyle p=2}$ ${\displaystyle p}$ ${\displaystyle p\geq 3}$ ${\displaystyle p}$ ${\displaystyle a}$ ${\displaystyle a^{-1}}$ ${\displaystyle a}$ ${\displaystyle a\equiv a^{-1}{\pmod {p}}}$ ${\displaystyle a\equiv \pm 1{\pmod {p}}}$ ${\displaystyle \pm 1}$ ${\displaystyle (p-1)!}$ ${\displaystyle 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}}.}$$

Demostración mediante el pequeño teorema de Fermat

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.

Demostración mediante los teoremas de Sylow

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.

Aplicaciones

Pruebas de primalidad

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 ]}

Residuos cuadráticos

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}}.}$$

Fórmulas para números primos

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

Función gamma p-ádica

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

Generalización de Gauss

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 }$

Véase también

• Wilson primo
• Tabla de congruencias

Notas

1. Porque si entonces , y si el primo divide a , entonces por el lema de Euclides divide a o a . ${\displaystyle a\equiv a^{-1}{\pmod {p}}}$ ${\displaystyle a^{2}-1\equiv 0{\pmod {p}}}$ ${\displaystyle p}$ ${\displaystyle a^{2}-1=(a-1)(a+1)}$ ${\displaystyle a-1}$ ${\displaystyle a+1}$

1. El libro universal de las matemáticas. David Darling, pág. 350.
2. O'Connor, John J.; Robertson, Edmund F. , "Abu Ali al-Hasan ibn al-Haytham", Archivo de Historia de las Matemáticas MacTutor , Universidad de St Andrews
3. Edward Waring, Meditationes Algebraicae (Cambridge, Inglaterra: 1770), página 218 (en latín). En la tercera edición (1782) de Meditationes Algebraicae de Waring , el teorema de Wilson aparece como el problema 5 en la página 380. En esa página, Waring afirma: "Hanc maxime elegantem primorum numerorum proprietatem invenit vir clarissimus, rerumque mathematicarum peritissimus Joannes Wilson Armiger". (Un hombre muy ilustre y hábil en matemáticas, el escudero John Wilson, descubrió esta elegante propiedad de los números primos.)
4. Joseph Louis Lagrange, "Demonstration d'un théorème nouveau concernant les nombres premiers" (Prueba de un nuevo teorema sobre los números primos), Nouveaux Mémoires de l'Académie Royale des Sciences et Belles-Lettres (Berlín), vol. 2, páginas 125-137 (1771).
5. Giovanni Vacca (1899) "Sui manoscritti inediti di Leibniz" (Sobre manuscritos inéditos de Leibniz), Bollettino di bibliografia e storia delle scienze matematiche ... (Boletín de bibliografía e historia de las matemáticas), vol. 2, páginas 113–116; ver página 114 (en italiano). Vacca cita los manuscritos matemáticos de Leibniz conservados en la Biblioteca Pública Real de Hannover (Alemania), vol. 3 B, paquete 11, página 10:

   Original  : Inoltre egli intravide anche il teorema di Wilson, come risulta dall'enunciato seguente:
   
   "Productus continuorum usque ad numerum qui antepraecedit datum divisus per datum relinquit 1 (vel complementum ad unum?) si datus sit primitivus. Si datus sit derivativus relinquet numerum qui cum dato habeat communem mensuram unitate majorem."
   
   Egli non giunse pero a dimostrarlo.

   Traducción  : Además, Leibniz también vislumbró el teorema de Wilson, como se muestra en la siguiente afirmación:
   
   "El producto de todos los números enteros anteriores al número entero dado, cuando se divide por el número entero dado, da 1 (¿o el complemento de 1?) si el número entero dado es primo. Si el número entero dado es compuesto, da un número que tiene un factor común con el número entero dado [que es] mayor que uno".
   
   Sin embargo, no logró demostrarlo.

   Véase también: Giuseppe Peano, ed., Formulaire de mathématiques , vol. 2, núm. 3, página 85 (1897).
6. Landau, dos pruebas del mismo. 78 ^{[ cita completa necesaria ]}
7. Gauss, DA, artículo 78

Referencias

Las Disquisitiones Arithmeticae han sido traducidas del latín ciceroniano de Gauss al inglés y al alemán. La edición alemana incluye todos sus artículos sobre teoría de números: todas las pruebas de reciprocidad cuadrática, la determinación del signo de la suma de Gauss, las investigaciones sobre reciprocidad bicuadrática y notas inéditas.

• Gauss, Carl Friedrich; Clarke, Arthur A. (1986), Disquisitiones Arithmeticae (segunda edición corregida), Nueva York: Springer , ISBN 0-387-96254-9(traducido al español){{citation}}: CS1 maint: postscript (link).
• Gauss, Carl Friedrich; Maser, H. (1965), Untersuchungen über hohere Arithmetik (Disquisitiones Arithmeticae y otros artículos sobre teoría de números) (2ª ed.), Nueva York: Chelsea, ISBN 0-8284-0191-8(traducido al alemán){{citation}}: CS1 maint: postscript (link).
• Landau, Edmund (1966), Teoría elemental de números , Nueva York: Chelsea.
• Ore, Øystein (1988). Teoría de números y su historia. Dover. pp. 259–271. ISBN 0-486-65620-9.

Enlaces externos

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