Movatterモバイル変換

[0]ホーム
URL:

Saltar para o conteúdo
Wikipédia
Busca

Teorema de Wilson

Origem: Wikipédia, a enciclopédia livre.

Texto adaptado dos respectivos artigos em inglês e espanhol.

EmÁlgebra eTeoria dos Números,o Teorema de Wilson afirma que umnúmero naturaln > 1 é umnúmero primo se, e apenas se, o produto de todos os inteiros positivos menores quen é um múltiplo den menos um. Isso quer dizer que (usando a notação daaritmética modular), ofatorial(n−1)!=1×2×3×⋯×(n−1){\displaystyle (n-1)!=1\times 2\times 3\times \cdots \times (n-1)} satisfaz

(n−1)! ≡−1(modn){\displaystyle (n-1)!\ \equiv \;-1{\pmod {n}}}

exatamente quandon é um número primo. Em outras palavras, qualquer númeron é um número primo, somente se, (n - 1)! + 1 é divisível porn.[1]

História

[editar |editar código-fonte]

O teorema foi declarado porIbn al-Haytham (c. 1000 DC),[2] e, no século 18, porJohn Wilson.[3]Edward Waring anunciou o teorema em 1770, embora nem ele nem seu aluno Wilson pudessem prová-lo.Lagrange deu a primeira prova em 1771.[4] Há evidências de que Leibniz também estava ciente do resultado um século antes, mas nunca o publicou.[5]

Exemplos

[editar |editar código-fonte]

Para cada um dos valores den de 2 a 30, a tabela a seguir mostra o número (n - 1)! e o resto quando (n - 1)! é dividido porn. (Na notação daaritmética modular, o resto quandom é dividido porn é escrito comom mod n.) A cor do fundo é azul para valoresprimos den e ouro para valorescompostos.

Tabela dos fatoriais e os restos modulon
n{\displaystyle n}(n−1)!{\displaystyle (n-1)!}
(sequênciaA000142 naOEIS)		(n−1)! mod n{\displaystyle (n-1)!\ {\bmod {\ }}n}
(sequênciaA061006 naOEIS)
211
322
462
5244
61200
77206
850400
9403200
103628800
11362880010
12399168000
1347900160012
1462270208000
15871782912000
1613076743680000
172092278988800016
183556874280960000
19640237370572800018
201216451004088320000
2124329020081766400000
22510909421717094400000
23112400072777760768000022
24258520167388849766400000
256204484017332394393600000
26155112100433309859840000000
274032914611266056355840000000
28108888694504183521607680000000
2930488834461171386050150400000028
3088417619937397019545436160000000

Provas

[editar |editar código-fonte]

Usando aritmética modular

[editar |editar código-fonte]

Por contradição, suponha que, para um númerop ≥ 2, que não é primo, cumpre-se a expressão:

(p−1)!≡−1(modp){\displaystyle (p-1)!\equiv -1{\pmod {p}}}

Dado quep não é primo, existea ∈ {2, ... ,p - 1} tal quea |p, ou seja, mcd(a,p) ≠ 1. A expressão anterior pode ser reescrita como

a⋅α≡−1(modp){\displaystyle a\cdot \alpha \equiv -1{\pmod {p}}}

sendo

α=∏1≤k<pk≠ak=1⋅2⋯(a−1)⋅(a+1)⋯(p−2)⋅(p−1).{\displaystyle \alpha =\prod _{1\leq k<p \atop k\neq a}k=1\cdot 2\cdots (a-1)\cdot (a+1)\cdots (p-2)\cdot (p-1).}

Aproveitando o fato de que (-1)2 = 1 (modp), tem-se que (a · a)2 = (-1)2 = 1 (modp). Pode-se deduzir, então, quea2 teminverso multiplicativo no módulop, o qual não pode ser verdadeiro pois mcd(a2,p) ≠ 1, de maneira que a suposição inicial de quep não é primo, é falsa.

Usando teoria de grupos

[editar |editar código-fonte]

Esta demonstração usa o fato de que sep é um número primo, então o conjunto de númerosG = (Z/pZ)× = {1, 2, ...p - 1} forma ungrupo sob multiplicação. Isto significa que, para cada elementoa deG, há um únicoinverso multiplicativob emG tal queab = 1 (modp). Sea =b (modp), entãoa2 = 1 (modp), que se podefatorar ema2 - 1 = (a + 1)(a - 1) = 0 (modp), e, posto quep é primo, entãoa = 1 ou -1 (modp), por exemploa = 1 oua =p - 1.

Em outras palavras, 1 ep - 1 são, cada um seu próprio inverso, mas para qualquer outro elemento deG há um inverso também emG, assim que, se tomamos todos os elementos deG em pares e multiplicamos todos eles juntos, o produto será igual a -1 (módulo p). Por exemplo, sep = 11, teremos que:

10!=1(10)(2⋅6)(3⋅4)(5⋅9)(7⋅8) ≡ −1 (mod 11).{\displaystyle 10!=1(10)(2\cdot 6)(3\cdot 4)(5\cdot 9)(7\cdot 8)\ \equiv \ -1\ ({\mbox{mod}}\ 11).\,}

As propriedades comutativas e associativas são usadas no procedimento acima. Todos os elementos do produto anterior terão a formag g -1 = 1 (modp) exceto 1 (p - 1), que estão no princípio do produto.

Sep = 2, o resultado é trivial e imediato.

Para demonstrar o inverso do teorema (ver a seção seguinte), suponhamos que acongruência cumpre-se para umnúmero composton. Note-se, então, quen tem umdivisor próprio|d com 1 <d <n. Claramente,d divide (n - 1)! mas, pela congruência,d também divide a (n - 1)! + 1, entãod divide 1, e se chega a uma contradição.

Usando polinômios

[editar |editar código-fonte]

Sejap um número primo. Consideremos o polinômio:

g(x):=(x−1)(x−2)⋯(x−(p−1)).{\displaystyle g(x):=(x-1)(x-2)\cdots (x-(p-1)).\,}

Recordemos que sef(x) é um polinômio não nulo de graud sobre umcorpoF, entãof(x) tem um máximo ded raízes emF, e recordemos que o conjunto de todos os restos módulo um primo, com as operações de soma y multiplicação, é um corpo. Agora, sendog(x)

f(x):=g(x)−(xp−1−1).{\displaystyle f(x):=g(x)-(x^{p-1}-1).\,}

Como os coeficientes de ordem superior se cancelam,f(x) é um polinômio de graup - 2 no máximo. Portanto, se tomarmos restos módulop,f(x) terá no máximop - 2 raízes módulop. No entanto, tendo em vista a definição def(x), segue-se, doPequeno Teorema de Fermat, que todo elemento 1, 2, ...,p - 1 é uma raiz def(x) (portanto,a fortiori, é uma raiz def(x) módulop). Isto é impossível, a menos quef(x) seja identicamente zero módulop, ou seja, a menos que cada coeficiente def(x) seja divisível porp.

Uma vez que o termo constante def(x) é justamente (p - 1)! + 1.

Recíproca

[editar |editar código-fonte]

O inverso do Teorema de Wilson Diz que para qualquernúmero composton > 5,

n divide (n - 1)!.

Deixamos o cason = 4, para o qual 3! não é divisível por 4 (é apenas divisível por 2).

De fato, seq é um fator primo den, tal quen =qa, os números

1, 2, ...,n - 1

incluindoa - 1 múltiplos deq. Portanto, as potências deq que dividem o fatorial são ao menosn/q - 1; e as potências que dividemn são no máximo

logn/logq.

A inequação:

logn/logq =n/q - 1

É verdade em geral, exceto para o casoq = 2 en = 4.

Teste de primalidade

[editar |editar código-fonte]

O Teorema de Wilson não se utiliza comoteste de primalidade na prática, uma vez que que para calcular (n - 1)! módulon para um númeron grande é caro (do ponto de vista computacional), e se conhecem testes mais simples e rápidos.

Usando o Teorema de Wilson, tem-se que, para cada número primop:

1⋅2⋯(p−1) ≡ −1 (mod p){\displaystyle 1\cdot 2\cdots (p-1)\ \equiv \ -1\ ({\mbox{mod}}\ p)}
1⋅(p−1)⋅2⋅(p−2)⋯n⋅(p−n) ≡ 1⋅(−1)⋅2⋅(−2)⋯n⋅(−n) ≡ −1 (mod p){\displaystyle 1\cdot (p-1)\cdot 2\cdot (p-2)\cdots n\cdot (p-n)\ \equiv \ 1\cdot (-1)\cdot 2\cdot (-2)\cdots n\cdot (-n)\ \equiv \ -1\ ({\mbox{mod}}\ p)}

ondep = 2n + 1. Isto se torna

∏j=1n j2 ≡(−1)n+1 (mod p).{\displaystyle \prod _{j=1}^{n}\ j^{2}\ \equiv (-1)^{n+1}\ ({\mbox{mod}}\ p).}

Assim, a primalidade do número se determina mediante osresíduo quadrático dep. Na verdade, isso pode ser usado para provar parte de outro resultado famoso: -1 é um quadrado (resíduo quadrático) modp sep = 1 (mod 4). Para a suposição,p = 4k + 1 para algum inteirok. Então, tomandon = 2k e substituindo, conclui-se que:

(∏j=12k j)2=∏j=12k j2 ≡(−1)2k+1 =−1 (mod p).{\displaystyle \left(\prod _{j=1}^{2k}\ j\right)^{2}=\prod _{j=1}^{2k}\ j^{2}\ \equiv (-1)^{2k+1}\ =-1\ ({\mbox{mod}}\ p).}

O teorema de Wilson foi usado para gerar fórmulas para números primos, mas é muito lento para ter qualquer valor prático.

Ver também

[editar |editar código-fonte]

Notas

[editar |editar código-fonte]
  1. ↑The Universal Book of Mathematics. David Darling, p. 350.
  2. ↑O'Connor, John J.;Robertson, Edmund F.,«Abu Ali al-Hasan ibn al-Haytham»,MacTutor History of Mathematics archive (em inglês),Universidade de St. Andrews 
  3. ↑Edward Waring,Meditationes Algebraicae (Cambridge, England: 1770), page 218 (in Latin). In the third (1782) edition of Waring'sMeditationes Algebraicae, Wilson's theorem appears as problem 5 onpage 380. On that page, Waring states: "Hanc maxime elegantem primorum numerorum proprietatem invenit vir clarissimus, rerumque mathematicarum peritissimus Joannes Wilson Armiger." (A man most illustrious and most skilled in mathematics, Squire John Wilson, found this most elegant property of prime numbers.)
  4. ↑Joseph Louis Lagrange,"Demonstration d'un théorème nouveau concernant les nombres premiers" (Proof of a new theorem concerning prime numbers),Nouveaux Mémoires de l'Académie Royale des Sciences et Belles-Lettres (Berlin), vol. 2, pages 125–137 (1771).
  5. ↑Giovanni Vacca (1899) "Sui manoscritti inediti di Leibniz" (On unpublished manuscripts of Leibniz),Bollettino di bibliografia e storia delle scienze matematiche ... (Bulletin of the bibliography and history of mathematics), vol. 2, pages 113–116; seepage 114 (in Italian). Vacca quotes from Leibniz's mathematical manuscripts kept at the Royal Public Library in Hanover (Germany), vol. 3 B, bundle 11, page 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.

    Translation : In addition, he [Leibniz] also glimpsed Wilson's theorem, as shown in the following statement:

    "The product of all integers preceding the given integer, when divided by the given integer, leaves 1 (or the complement of 1?) if the given integer be prime. If the given integer be composite, it leaves a number which has a common factor with the given integer [which is] greater than one."

    However, he didn't succeed in proving it.

    See also: Giuseppe Peano, ed.,Formulaire de mathématiques, vol. 2, no. 3,page 85 (1897).
Princípios gerais
Áreas
Conceitos-chave
Conceitos avançados
Principais teóricos
Obtida de "https://pt.wikipedia.org/w/index.php?title=Teorema_de_Wilson&oldid=67940175"
Categoria:
Categoria oculta:
[8]ページ先頭
©2009-2025 Movatter.jp