Teorema de Wilson
Em matemática , mais precisamente em aritmética elementar , o teorema de Wilson afirma que um inteiro p maior que 1 é primo se e somente se o fatorial de p - 1 é congruente com -1 módulo p . Esta caracterização dos números primos é bastante anedótica e não constitui um teste de primalidade eficaz. Seu principal interesse está em sua história e na relativa simplicidade de suas afirmações e provas.
Declaração e exemplos
Estados
Teorema de Wilson - Um inteiro p estritamente maior que 1 é um número primo se e somente se ele se divide ( p - 1)! + 1, ou seja, se e somente se:
(p-1)!+1≡0(modp).{\ displaystyle (p-1)! + 1 \ equiv 0 {\ pmod {p}}.}
Aqui, o símbolo “! "Designa a função fatorial e o símbolo". ≡. (mod.) ”designa congruência sobre números inteiros .
Exemplos
- Se p for igual a 2, então ( p - 1)! + 1 é igual a 2, um múltiplo de 2.
- Se p for igual a 3, então ( p - 1)! + 1 é igual a 3, um múltiplo de 3.
- Se p for igual a 4, então ( p - 1)! +1 é igual a 7, o que não é múltiplo de 4.
- Se p for igual a 5, então ( p - 1)! +1 é igual a 25, um múltiplo de 5.
- Se p for igual a 6, então ( p - 1)! +1 é igual a 121, que não é múltiplo de 6.
- Se p for igual a 17, então ( p - 1)! + 1 é igual a 20 922 789 888 001, um múltiplo de 17 porque 17 × 1 230 752 346 353 = 20 922 789 888 001 .
História
O primeiro texto atualmente conhecido que se refere a esse resultado é devido ao matemático árabe Alhazen (965-1039) . Este teorema é conhecida a partir da XVII th século na Europa. Gottfried Wilhelm Leibniz (1646-1716) refere-se a esse resultado sem demonstrá-lo. John Wilson redescobre o que acredita ser uma conjectura e compartilha sua descoberta com seu professor Edward Waring , que publicou essa conjectura em 1770.
Joseph-Louis Lagrange apresentou duas primeiras demonstrações em 1771, depois Leonhard Euler uma terceira em 1773. Usando notações da aritmética modular , Carl Friedrich Gauss (1777-1855) reformulou a demonstração de Euler e deu uma quarta.
Manifestações
Primeiro, se p é um número composto , ele tem um divisor d tal que 1 < d < p ; então, ( p - 1)! é divisível por d, portanto ( p - 1)! + 1 não é e a fortiori, ( p - 1)! + 1 ≢ 0 (mod p ). Na verdade, podemos mostrar que se p (composto) for diferente de 4, então ( p - 1)! é até divisível por p . De fato, p é então escrito ab com 2 ≤ a ≤ b (com pelo menos uma dessas desigualdades estritas desde p ≠ 4) ep = ab ≥ 2 b ≥ a + b (com uma dessas desigualdades estritas), portanto, p > a + b , de modo que ( p - 1)! é divisível por ( a + b )!, ele próprio divisível por a ! b ! portanto, por ab .
Vamos passar ao contrário. Suponhamos que p ' . O anel ℤ / p ℤ é então um campo comutativo , ou seja, módulo p , as classes de congruência de 1, 2, ..., p - 1 são invertíveis (é apenas a identidade de Bézout ). Denotamos este campo F p . As demonstrações abaixo assumem o princípio das quatro demonstrações históricas, mas são apresentadas com a notação “moderna” (introduzida por Gauss) de congruências. Eles podem ser reformulados sem ele.
Demonstrações de Lagrange
- Lagrange primeiro usa o polinômioP(x)=(x+1)(x+2)⋯(x+p-1).{\ displaystyle P (x) = (x + 1) (x + 2) \ cdots (x + p-1).}Ele o expande e determina seus coeficientes passo a passo usando a propriedade(x+1)P(x+1)=(x+p)P(x).{\ displaystyle (x + 1) P (x + 1) = (x + p) P (x).}Ele então mostra, passo a passo, que, quando p é primo, todos os coeficientes - exceto o primeiro que vale 1 e o último que vale ( p - 1)! - são múltiplos de p .
Então, ainda usando a mesma igualdade, ele observa que o último coeficiente multiplicado por p - 1 é igual à soma de todos os outros e deduz que ( p - 1)! + 1 é um múltiplo de p .
- Depois de notar que o pequeno teorema de Fermat também é deduzido desses cálculos, ele mostra que, inversamente, esse teorema fornece "outra prova daquele do Sr. Wilson muito mais simples" , ao expressar de duas maneiras a ( p - 1) -ésima diferença finita de a sequência 1 p –1 , 2 p –1 , ..., p p –1 , então aplicando o teorema de Fermat e a fórmula binomial :(p-1)!=∑eu=0p-1(-1)eu(p-1eu)(p-eu)p-1≡(modp)∑eu=1p-1(-1)eu(p-1eu)=(1-1)p-1-1=-1{\ displaystyle (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.}
Observação
Lagrange observa ainda que para qualquer número inteiro ímpar n ,, o que, juntamente com o teorema de Wilson, prova que para qualquer número primo ímpar p ,
(não-1)!≡(-1)não-12(1.2.3...não-12)2(modnão){\ displaystyle (n-1)! \ equiv (-1) ^ {\ frac {n-1} {2}} \ left (1.2.3 \ dots {\ frac {n-1} {2}} \ right ) ^ {2} {\ pmod {n}}}E se p-12 é mesmo então-1≡(1.2.3...p-12)2(modp).{\ displaystyle {\ text {si}} {\ frac {p-1} {2}} {\ text {é par então}} - 1 \ equiv \ left (1.2.3 \ dots {\ frac {p-1 } {2}} \ right) ^ {2} {\ pmod {p}}.}Assim, –1 é um
módulo quadrado p se (e somente se) p ≡ 1 mod 4. É a primeira
lei complementar da
lei da reciprocidade quadrática . Ele desempenha um papel central no
teorema dos
dois quadrados .
Demonstração de Euler
Euler usa o fato de que o grupo multiplicativo F p * é cíclico , ou seja, gerado por uma classe particular a , o que equivale a dizer que as primeiras p - 1 potências de a (quando o expoente varia de 0 em p - 2) formam os elementos deste grupo. Ao fazer seu produto, portanto, temos:
(p-1)!¯=no0no1...nop-2=nonão, {\ displaystyle {\ overline {(p-1)!}} = a ^ {0} a ^ {1} \ ldots a ^ {p-2} = a ^ {n}, ~}
onde o expoente n é calculado como a soma de uma sequência aritmética :
não=∑k=0p-2k=(p-1)(p-2)2. {\ displaystyle n = \ sum _ {k = 0} ^ {p-2} k = {(p-1) (p-2) \ over 2}. ~}
O número primo p pode ser considerado ímpar (porque para p = 2 o teorema é válido diretamente). Assim, p - 1 não divide n , enquanto divide 2 n . Em outras palavras, a n é de ordem 2. Agora, no campo F p , as raízes do polinômio X 2 - 1 = ( X - 1 ) ( X + 1 ) são 1 e - 1 , portanto, a n = - 1 .
Gauss escreve esta prova em um contexto mais geral, mostrando assim que módulo um número p não necessariamente privilegiada, o produto dos poderes de um invertível um é igual a 1 ou -1, conforme a paridade da ordem multiplicativo de um .
Prova de Gauss
O princípio, emprestado de Euler, consiste em eliminar, no produto dos p - 1 elementos de F p *, cada produto de um elemento pelo seu inverso, com exceção dos elementos que são seus próprios inversos: 1 e - 1 . Quando eliminamos, no produto, os pares de inversos mútuos cujo produto é igual a 1 , apenas essas duas classes particulares permanecem, portanto
(p-1)!¯=-1¯ 1¯=-1¯.{\ displaystyle {\ overline {(p-1)!}} = {\ overline {-1}} \ {\ overline {1}} = - {\ overline {1}}.}
Demonstração de petr
O matemático tcheco Karel Petr deu em 1905 uma prova geométrica do teorema. Ele considera todos os polígonos cujos vértices são os p vértices de um dado polígono convexo regular, p um número primo. Existem ( p -1)! Entre eles, p -1 são regulares. Petr mostra que os outros são congruentes p com p , de modo que seu número é um múltiplo inteiro de p , que ele denota Np . Então ( p -1)! é igual a p -1+ Np , em outras palavras ( p -1)! é igual a -1 para um múltiplo de p , que é o teorema de Wilson.
Generalização
Em um grupo abeliano finito denotado por multiplicação, o produto dos elementos é igual a neutro, a menos que haja exatamente um elemento de ordem 2, caso em que o produto é igual a este elemento.
Em particular :
- o produto dos elementos não nulos do corpo finito F p n é sempre igual a –1 (que vale 1 se p = 2);
- para qualquer inteiro n > 1, o produto dos inteiros entre 1 e n e primo com n é congruente com -1 módulo n se n = 4, ou uma potência de um primeiro ímpar, ou o dobro de tal potência, e congruente para 1 caso contrário.
Ciência da Computação
Sendo os fatoriais bastante lentos para calcular, é raro usar este teorema como teste de primalidade, por outro lado podemos aumentar a velocidade de cálculo, sem alterar a complexidade do algoritmo:
Seja n um número natural:
import math
def isPrime(n):
if n == 4: return False
return bool(math.factorial(n>>1)%n)
Notas e referências
-
Esta fórmula é equivalente a ( p - 1)! ≡ p - 1 (mod p ), pois –1 ≡ p - 1 (mod p ).
-
Alhazen, Opuscula .
-
Roshdi Rashed , Between Arithmetic and Algebra: Research on the History of Arab Mathematics , Paris, 1984.
-
(La) Edward Waring, Meditações de Edward Waring , Cambridge J. Archdeacon, 1770.
-
(em) D. Weeks, Meditations algebraicae , trabalho de tradução Waring, Providence RI 1991.
-
Joseph-Louis Lagrange, “ demonstração de um novo teorema sobre números primos ”, Nouvelles Mémoires de l' Académie Royale des Sciences et Belles-Lettres , Berlim, 1771 ( publicada em 1773 ), p. 125-137 .
-
(la) Leonard Euler, “Miscellanea analytica”, Opuscula Analytica , volume I, 1783, p. 329-330 , apresentado à St. Petersburg Academy em 15 de novembro de 1773, de acordo com o Darthmouth College (Enestrom número 560) .
-
Carl Friedrich Gauss ( traduzido do latim por M. Poullet-Delisle), pesquisa Aritmética [ " Disquisitiones Arithmeticae "], Courcier,1807( 1 st ed. 1801) ( linha de leitura ) , p. 55-57 (§ 75-78).
-
Gauss provavelmente o havia notado - cf. (pt) Stephen Hawking , Deus criou os inteiros: os avanços matemáticos que mudaram a história , Running Press,2007( leia online ) , p. 594- mas este complemento não parece ter merecido uma alusão em suas Disquisitiones .
-
Para uma alternativa, consulte (em) Daniel Rosenthal, David Rosenthal e Peter Rosenthal, A Readable Introduction to Real Mathematics , Springer ,2014( leia online ) , p. 38, Th. 5.2.2.
-
Na verdade, é um coeficiente binomial, portanto, um número inteiro. Outras provas podem ser vistas na Teoria Fatorial # Numérica .(no+b)!no!b!{\ displaystyle {\ frac {(a + b)!} {a! b!}}}
-
Uma demonstração "manual" posada em forma de exercício com a correção pelo site maths-express.com.
-
Lagrange é explicitamente inspirado pela prova de Euler ( E241 ) do lema que lhe permitiu completar sua prova do teorema dos dois quadrados.
-
Gauss 1807 , § 75. Ver também § 76, onde Euler é mencionado.
-
(in) Andre Weil , Teoria dos Números: uma abordagem ao longo da história de Hammurabi a Legendre [ edições de varejo ], p. 201 : " Eu. I-3. 507, 525 ” , isto é (la) L. Euler, Opuscula analytica , vol. 1, " Observationes circa divisionem quadratorum per numeros primos ", E552 ,1783, p. 64-84(p. 77) e " Disquisitio precisatior circa residua ex divisione quadratorum altiorumque potestatum, per numeros primos relicta ", E554 ,1783, p. 121-156 (p. 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 ( leia online ).
-
Vincent Beck, " Variações em torno do teorema de Wilson " , 2020-2021 , corolário 10.
-
Esse resultado é declarado em Gauss 1807 , p. 57 (§ 78) com algumas faixas de demonstração. Beck 2020-2021 , Corolário 11, prova isso usando a estrutura de grupo de unidades de ℤ / n ℤ .
Veja também
Artigos relacionados
Bibliografia
Pierre Samuel , teoria algébrica dos números [ detalhe da edição ]
Link externo
Gilles Auriol, Sobre a soma dos quadrados . Em particular, existem duas provas do teorema de Wilson: a de Gauss ("versão elementar, acessível a um aluno no terminal S ") e uma envolvendo um polinômio semelhante ao de Lagrange, mas de uma maneira diferente ("versão da licença ")
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">