Teorema de Wilson

En matemáticas , más precisamente en aritmética elemental , el teorema de Wilson establece que un entero p mayor que 1 es primo si y sólo si el factorial de p - 1 es congruente con –1 módulo p . Esta caracterización de los números primos es bastante anecdótica y no constituye una prueba de primalidad eficaz. Su principal interés radica en su historia y en la relativa sencillez de su enunciado y sus pruebas.

Declaración y ejemplos

Estados

Teorema de Wilson - ¡ Un entero p estrictamente mayor que 1 es un número primo si y solo si divide ( p - 1)! + 1, es decir, si y solo si:

(p-1)! + 1 \ equiv 0 {\ pmod p}.

Aquí, el símbolo “! "Designa la función factorial y el símbolo". ≡. (mod.) ”designa la congruencia entre números enteros .

Ejemplos de

Si p es igual a 2, entonces ( p - 1)! + 1 es igual a 2, un múltiplo de 2.
Si p es igual a 3, entonces ( p - 1)! + 1 es igual a 3, un múltiplo de 3.
Si p es igual a 4, entonces ( p - 1)! + 1 es igual a 7, que no es múltiplo de 4.
Si p es igual a 5, entonces ( p - 1)! +1 es igual a 25, un múltiplo de 5.
Si p es igual a 6, entonces ( p - 1)! +1 es igual a 121, que no es múltiplo de 6.
Si p es igual a 17, entonces ( p - 1)! + 1 es igual a 20 922 789 888 001, un múltiplo de 17 porque 17 × 1230752346353 = 20 922 789 888 001 .

Historia

El primer texto conocido actualmente que hace referencia a este resultado se debe al matemático árabe Alhazen (965-1039) . Este teorema se conoce a partir del XVII ° siglo en Europa. Gottfried Wilhelm Leibniz (1646-1716) se refiere a este resultado sin demostrarlo. John Wilson redescubre lo que cree que es una conjetura y comparte su descubrimiento con su maestro Edward Waring , quien publicó esta conjetura en 1770.

Joseph-Louis Lagrange presentó dos primeras demostraciones en 1771, luego Leonhard Euler una tercera en 1773. Utilizando notaciones de la aritmética modular , Carl Friedrich Gauss (1777-1855) reformuló la demostración de Euler y dio una cuarta.

Demostraciones

Primero, si p es un número compuesto , tiene un divisor d tal que 1 < d < p ; entonces, ( p - 1)! es divisible por d por lo tanto ( p - 1)! + 1 no es y a fortiori, ( p - 1)! + 1 ≢ 0 (mod p ). De hecho, podemos demostrar que si p (compuesto) es diferente de 4, ¡entonces ( p - 1)! incluso es divisible por p . De hecho, p se escribe entonces ab con 2 ≤ a ≤ b (con al menos una de estas desigualdades estrictas ya que p ≠ 4) y p = ab ≥ 2 b ≥ a + b (con una de estas desigualdades estricta) por lo tanto p > a + b , entonces ( p - 1)! es divisible por ( a + b )!, él mismo divisible por a ! b ! por lo tanto por ab .

Pasemos a lo contrario. Suponemos p primo. El anillo ℤ / p ℤ es entonces un campo conmutativo , es decir que módulo p , las clases de congruencia de 1, 2,…, p - 1 son invertibles (es solo la identidad de Bézout ). Denotamos este campo F p . Las siguientes demostraciones retoman el principio de las cuatro demostraciones históricas, pero se presentan con la notación "moderna" (introducida por Gauss) de congruencias. Pueden reformularse sin él.

Demostraciones de Lagrange

Lagrange primero usa el polinomio $P (x) = (x + 1) (x + 2) \ cdots (x + p-1).$ Lo expande y determina sus coeficientes paso a paso usando la propiedad $(x + 1) P (x + 1) = (x + p) P (x).$ Luego muestra, paso a paso, que, cuando p es primo, todos los coeficientes, excepto el primero que vale 1 y el último que vale ( p - 1). - son múltiplos de p .
Luego, aún usando la misma igualdad, observa que el último coeficiente multiplicado por p - 1 es igual a la suma de todos los demás y deduce que ( p - 1). + 1 es un múltiplo de p .
Después de notar que el pequeño teorema de Fermat también se deduce de estos cálculos, muestra que, a la inversa, este teorema proporciona "otra prueba de la del Sr. Wilson mucho más simple" , al expresar de dos maneras la ( p - 1) -ésima diferencia finita de la secuencia 1 p –1 , 2 p –1 ,…, p p –1 , luego aplicando el teorema de Fermat y la fórmula binomial : $(p-1)! = \ sum _ {{i = 0}} ^ {{p-1}} (- 1) ^ {i} {\ binom {p-1} i} (pi) ^ {{p -1}} {\ underset {{\ pmod p}} {\ equiv}} \ sum _ {{i = 1}} ^ {{p-1}} (- 1) ^ {i} {\ binom {p -1} i} = (1-1) ^ {{p-1}} - 1 = -1.$

Nota Lagrange observa además que para cualquier número entero impar n ,, que, junto con el teorema de Wilson, prueba que para cualquier número primo impar p ,

{\ displaystyle (n-1)! \ equiv (-1) ^ {\ frac {n-1} {2}} \ left (1.2.3 \ dots {\ frac {n-1} {2}} \ right ) ^ {2} {\ pmod {n}}}

{\ displaystyle {\ text {si}} {\ frac {p-1} {2}} {\ text {es par entonces}} - 1 \ equiv \ left (1.2.3 \ dots {\ frac {p-1 } {2}} \ right) ^ {2} {\ pmod {p}}.}

Por tanto, –1 es un cuadrado módulo p si (y sólo si) p ≡ 1 mod 4. Es la primera ley complementaria de la ley de reciprocidad cuadrática . Desempeña un papel central en el teorema de los dos cuadrados .

Demostración de Euler

Euler usa el hecho de que el grupo multiplicativo F p * es cíclico , es decir, generado por una clase particular a , lo que equivale a decir que las primeras p - 1 potencias de a (cuando el exponente varía de 0 en p - 2) forman los elementos de este grupo. Por lo tanto, al fabricar su producto tenemos:

\ overline {(p-1)!} = a ^ {0} a ^ {1} \ ldots a ^ {{p-2}} = a ^ {n}, ~

donde el exponente n se calcula como la suma de una secuencia aritmética :

n = \ sum _ {{k = 0}} ^ {{p-2}} k = {(p-1) (p-2) \ over 2}. ~

Se puede suponer que el número primo p es impar (porque para p = 2 el teorema se cumple directamente). Por lo tanto, p - 1 no divide n , mientras que divide 2 n . En otras palabras, a n es de orden 2. Ahora, en el campo F p , las raíces del polinomio X 2 - 1 = ( X - 1 ) ( X + 1 ) son 1 y - 1 , por lo tanto a n = - 1 .

Gauss escribe esta demostración en un contexto más general, mostrando así que módulo un número p no necesariamente primo, el producto de las potencias de un invertible a es igual a 1 o –1, según la paridad del orden multiplicativo de a .

Prueba de Gauss

El principio, tomado de Euler, consiste en eliminar, en el producto de los p - 1 elementos de F p *, cada producto de un elemento por su inverso, con excepción de los elementos que son su propio inverso: 1 y - 1 . Cuando eliminamos, en el producto, los pares de inversos mutuos cuyo producto es igual a 1 , solo quedan estas dos clases particulares, por lo tanto

\ overline {(p-1)!} = \ overline {-1} \ \ overline 1 = - \ overline 1.

Demostración de Petr

El matemático checo Karel Petr dio en 1905 una demostración geométrica del teorema. Considera todos los polígonos cuyos vértices son los p vértices de un polígono convexo regular dado, p un número primo. ¡Hay ( p -1)! Entre ellos, p -1 son regulares. Shows Petr que los demás son congruentes p a p , de modo que su número es un múltiplo entero de p , que indica Np . ¡Entonces ( p -1)! es igual a p -1+ Np , dicho de otro modo ( p -1)! es igual a -1 a un múltiplo de p , que es el teorema de Wilson.

Generalización

En un grupo abeliano finito denotado por multiplicación, el producto de los elementos es igual a neutro, a menos que haya exactamente un elemento de orden 2, en cuyo caso el producto es igual a este elemento.

En particular :

el producto de los elementos distintos de cero del campo finito F p n siempre es igual a –1 (que vale 1 si p = 2);
para cualquier número entero n > 1, el producto de los números enteros entre 1 y n y primos con n es congruente con –1 módulo n si n = 4, o una potencia de un primer impar, o el doble de dicha potencia, y congruente a 1 en caso contrario.

Ciencias de la Computación

Siendo los factoriales bastante lentos de calcular, es raro usar este teorema como prueba de primalidad, por otro lado podemos incrementar la velocidad de cálculo, sin cambiar la complejidad del algoritmo:

Sea n un número natural:

import math def isPrime(n): if n == 4: return False return bool(math.factorial(n>>1)%n)

Notas y referencias

Esta fórmula es equivalente a ( p - 1)! ≡ p - 1 (mod p ), ya que –1 ≡ p - 1 (mod p ).
Alhazen, Opuscula .
Roshdi Rashed , Between Arithmetic and Algebra: Research on the History of Arab Mathematics , París, 1984.
(La) Edward Waring, Edward Waring Meditationes , Cambridge J. Archdeacon, 1770.
(in) D. Weeks, Meditations algebraicae , trabajo de traducción Waring, Providence RI 1991.
Joseph-Louis Lagrange, “ Demostración de un nuevo teorema referente a los números primos ”, Nouvelles Mémoires de l' Académie Royale des Sciences et bellas letras , Berlín, 1771 ( publicada en 1773 ), p. 125-137 .
(la) Leonard Euler, “Miscellanea Analytica”, Opuscula Analytica , volumen I, 1783, p. 329-330 , presentado a la Academia de San Petersburgo el 15 de noviembre de 1773, según Darthmouth College (Enestrom número 560) .
Carl Friedrich Gauss ( traducido del latín por M. Poullet-Delisle), la investigación aritmética [ " Disquisitiones Arithmeticae "], Courcier,1807( 1 st ed. 1801) ( línea de leer ) , p. 55-57 (§ 75-78).
Gauss probablemente lo había notado - cf. (en) Stephen Hawking , Dios creó los enteros: los avances matemáticos que cambiaron la historia , Running Press,2007( leer en línea ) , pág. 594-pero este complemento no parece haber merecido una alusión en sus Disquisitiones .
Para una alternativa, ver (en) Daniel Rosenthal, David Rosenthal y Peter Rosenthal, A Readable Introduction to Real Mathematics , Springer ,2014( leer en línea ) , pág. 38, Th. 5.2.2.
De hecho, es un coeficiente binomial, por lo tanto, un número entero. Otras pruebas se pueden ver en Teoría de números factorial # . ${\ displaystyle {\ frac {(a + b)!} {a! b!}}}$
Una demostración "manual" planteada en forma de ejercicio con la corrección del sitio maths-express.com.
Lagrange se inspira explícitamente en la demostración de Euler ( E241 ) del lema que le permitió completar su demostración del teorema de los dos cuadrados.
Gauss 1807 , § 75. Ver también § 76, donde se menciona a Euler.
(en) Andre Weil , Teoría de números: un enfoque a través de la historia desde Hammurabi hasta Legendre [ ediciones minoristas ], p. 201 : " Eu. I-3. 507, 525 ” , es decir (la) L. Euler, Opuscula analytica , vol. 1, " Observaciones circa divisionem quadratorum per numeros primos ", E552 ,1783, p. 64-84(p. 77) y " Disquisitio exacttior circa residua ex divisione quadratorum altiorumque potestatum, per numeros primos relicta ", E554 ,1783, p. 121-156 (pág. 156).
(cs) Karel Petr, " Geometrický důkaz poučky Wilsonovy " , Časopis pro pěstování matematiky a fysiky , vol. 34, n o 21905, p. 164-166 ( leer en línea ).
Vincent Beck, “ Variaciones en torno al teorema de Wilson ” , 2020-2021 , corolario 10.
Este resultado se establece en Gauss 1807 , p. 57 (§ 78) con algunas pistas de demostración. Beck 2020-2021 , Corolario 11, lo demuestra utilizando la estructura de grupo de unidades de ℤ / n ℤ .

Ver también

Bibliografía

Pierre Samuel , Teoría algebraica de números [ detalle de la edición ]

Enlace externo

Gilles Auriol, Sobre las sumas de cuadrados . En particular, encontramos dos demostraciones del teorema de Wilson: la de Gauss ("versión elemental, accesible a un estudiante en terminal S ") y otra que involucra un polinomio similar al de Lagrange, pero de forma diferente ("versión de licencia ")