En 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
exactamente cuando n es un número primo. En otras palabras, cualquier número n es un número primo si, y solo si, ( n - 1). + 1 es divisible por n . [1]
Historia
Este teorema fue establecido por Ibn al-Haytham (c. 1000 dC), [2] y, en el siglo XVIII, por John Wilson . [3] Edward Waring anunció el teorema en 1770, aunque ni él ni su alumno Wilson pudieron probarlo. Lagrange dio la primera prueba en 1771. [4] Hay evidencia de que Leibniz también estaba al tanto del resultado un siglo antes, pero nunca lo publicó. [5]
Ejemplo
Para cada uno de los valores de n de 2 a 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 la aritmética modular , el resto cuando m se divide por n se escribe m mod n .) El color de fondo es azul para los valores primos de n y dorado para los valores compuestos .
(secuencia A000142 en la OEIS ) | (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 |
dieciséis | 1307674368000 | 0 |
17 | 20922789888000 | dieciséis |
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 |
Pruebas
Ambas demostraciones (para módulos primos) a continuación utilizan el hecho de que las clases de residuos módulo un número primo son un campo; consulte el artículo campo primo para obtener más detalles. [6] El teorema de Lagrange , que establece que en cualquier campo un polinomio de grado n tiene como máximo n raíces , es necesario para ambas demostraciones.
Módulo compuesto
Si n es compuesto, es divisible por algún número primo q , donde 2 ≤ q ≤ n - 2 . Porque divide , dejar por algún entero . ¡Supongamos, en aras de la contradicción, que ( n - 1)! eran congruentes con −1 (mod n ) donde n es compuesto. ¡Entonces (n-1)! también sería congruente con −1 (mod q ) como implica que por algún entero que muestra (n-1)! siendo congruente con -1 (mod q). ¡Pero ( n - 1)! ≡ 0 (mod q ) por el hecho de que q es un término en (n-1)! haciendo (n-1)! un múltiplo de q. Ahora se llega a una contradicción.
De hecho, más es verdad. Con la única excepción de 4, donde 3! = 6 ≡ 2 (mod 4), si n es compuesto entonces ( n - 1)! es congruente con 0 (mod n ). La demostración se divide en dos casos: Primero, si n se puede factorizar como el producto de dos números desiguales, n = ab , donde 2 ≤ a < b ≤ n - 2, entonces tanto a como b aparecerán en el producto 1 × 2 × ... × ( n - 1) = ( n - 1)! y ( n - 1)! será divisible por n . Si n no tiene tal factorización, entonces debe ser el cuadrado de algún primo q , q > 2. Pero entonces 2 q < q 2 = n , tanto q como 2 q serán factores de ( n - 1)! Y nuevamente n divide ( n - 1) !.
Módulo primo
- Prueba elemental
El resultado es trivial cuando p = 2 , así que suponga que p es un primo impar, p ≥ 3 . Puesto que las clases de residuos (mod p ) son un campo, cada distinto de cero una tiene un inverso multiplicativo único, un -1 . El teorema de Lagrange implica que los únicos valores de a para los cuales a ≡ a −1 (mod p ) son a ≡ ± 1 (mod p ) (porque la congruencia a 2 ≡ 1 puede tener como máximo dos raíces (mod p )). Por lo tanto, con la excepción de ± 1, los factores de ( p - 1)! se pueden organizar en pares desiguales, [7] donde el producto de cada par es ≡ 1 (mod p ) . Esto prueba el teorema de Wilson.
Por ejemplo, si p = 11 ,
- Prueba usando el pequeño teorema de Fermat
Nuevamente, el resultado es trivial para p = 2, así que suponga que p es un primo impar, p ≥ 3 . Considere el polinomio
¡g tiene grado p - 1 , término inicial x p - 1 y término constante ( p - 1)! . Sus raíces p - 1 son 1, 2, ..., p - 1 .
Ahora considera
h también tiene grado p - 1 y término inicial 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 .
Finalmente, considere
f tiene un grado como máximo p - 2 (ya que los términos iniciales se cancelan), y el 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.
- Prueba usando 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 , a saber, los p -ciclos. Por otro lado, cada subgrupo p de Sylow en es una copia de . Por lo tanto, se deduce que el número de subgrupos p de Sylow es. El tercer teorema de Sylow implica
Multiplicar ambos lados por ( p - 1) da
es decir, el resultado.
Aplicaciones
Pruebas de primordialidad
En la práctica, el teorema de Wilson es inútil como prueba de primalidad porque calcular ( n - 1)! módulo n para grandes n es computacionalmente complejo , y mucho más rápido de primalidad se conocen pruebas (de hecho, incluso la división de prueba es considerablemente más eficiente).
Residuos cuadráticos
Usando el teorema de Wilson, para cualquier primo impar p = 2 m + 1 , podemos reorganizar 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 . Supongamos que p = 4 k + 1 para algún entero k . Entonces podemos tomar m = 2 k arriba, y concluimos que ( m !) 2 es congruente con (−1).
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 un valor práctico.
función gamma p-ádica
El teorema de Wilson permite definir la función gamma p-ádica .
Generalización de Gauss
donde p representa un primo impar yun número entero positivo. Los valores de m para los que el producto es −1 son precisamente aquellos en los que existe una raíz primitiva módulo m .
Esto se generaliza aún más al hecho de que en cualquier grupo abeliano finito , o el producto de todos los elementos es la identidad, o hay precisamente un elemento a de orden 2 (pero no ambos). En el último caso, el producto de todos los elementos es igual a a .
Ver también
Notas
- ^ El libro universal de matemáticas. David Darling, pág. 350.
- ^ O'Connor, John J .; Robertson, Edmund F. , "Abu Ali al-Hasan ibn al-Haytham" , archivo MacTutor de Historia de las Matemáticas , Universidad de St Andrews.
- ^ 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 problema 5 en la página 380 . En esa página, Waring afirma: "Hanc maxime elegantem primorum numerorum proprietatem invenit vir clarissimus, rerumque mathicarum peritissimus Joannes Wilson Armiger". (El hombre más ilustre y más hábil en matemáticas, Squire John Wilson, encontró esta propiedad más elegante de los números primos).
- ^ Joseph Louis Lagrange, "Demonstration d'un théorème nouveau concernnant les nombres premiers" (Prueba de un nuevo teorema sobre 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).
- ↑ 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; consulte la página 114 (en italiano). Vacca cita de 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 Suppleum 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.
Véase también: Giuseppe Peano, ed., Formulaire de mathématiques , vol. 2, no. 3, página 85 (1897).Traducción : Además, él [Leibniz] también vislumbró el teorema de Wilson, como se muestra en el siguiente enunciado:
"El producto de todos los enteros que preceden al entero dado, cuando se divide por el entero dado, deja 1 (¿o el complemento de 1?) Si el entero dado debe ser primo. Si el entero dado es compuesto, deja un número que tiene un factor común con el entero dado [que es] mayor que uno ".
Sin embargo, no logró demostrarlo. - ^ Landau, dos pruebas de thm. 78
- ^ Cuando n = 3, los únicos factores son ± 1
- ^ Gauss, DA, art. 78
Referencias
The Disquisitiones Arithmeticae se ha traducido 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 la reciprocidad bicuadrática y notas inéditas.
- Gauss, Carl Friedrich; Clarke, Arthur A. (1986), Disquisitiones Arithemeticae (segunda edición corregida), Nueva York: Springer , ISBN 0-387-96254-9 (traducido al inglés)CS1 maint: posdata ( enlace ).
- Gauss, Carl Friedrich; Maser, H. (1965), Untersuchungen über hohere Arithmetik (Disquisitiones Arithemeticae y otros artículos sobre teoría de números) (2a ed.), Nueva York: Chelsea, ISBN 0-8284-0191-8 (traducido al alemán)CS1 maint: posdata ( enlace ).
- Landau, Edmund (1966), Teoría de números elemental , Nueva York: Chelsea.
- Ore, Øystein (1988). Teoría de números y su historia . Dover. págs. 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