Saltar para o conteúdo

Teorema de Wilson

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

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

Em Álgebra e Teoria dos Números, o Teorema de Wilson afirma que um número natural n > 1 é um número primo se, e apenas se, o produto de todos os inteiros positivos menores que n é um múltiplo de n menos um. Isso quer dizer que (usando a notação da aritmética modular), o fatorial satisfaz

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

O teorema foi declarado por Ibn al-Haytham (c. 1000 DC),[2] e, no século 18, por John 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]

Para cada um dos valores de n de 2 a 30, a tabela a seguir mostra o número (n - 1)! e o resto quando (n - 1)! é dividido por n. (Na notação da aritmética modular, o resto quando m é dividido por n é escrito como m mod n.) A cor do fundo é azul para valores primos de n e ouro para valores compostos.

Tabela dos fatoriais e os restos modulo n

(sequência A000142 na OEIS)

(sequência A061006 na 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
16 1307674368000 0
17 20922789888000 16
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

Usando aritmética modular

[editar | editar código-fonte]

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

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

sendo

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

Usando teoria de grupos

[editar | editar código-fonte]

Esta demonstração usa o fato de que se p é um número primo, então o conjunto de números G = (Z/pZ)× = {1, 2, ... p - 1} forma un grupo sob multiplicação. Isto significa que, para cada elemento a de G, há um único inverso multiplicativo b em G tal que ab = 1 (mod p). Se a = b (mod p), então a2 = 1 (mod p), que se pode fatorar em a2 - 1 = (a + 1)(a - 1) = 0 (mod p), e, posto que p é primo, então a = 1 ou -1 (mod p), por exemplo a = 1 ou a = p - 1.

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

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

Se p = 2, o resultado é trivial e imediato.

Para demonstrar o inverso do teorema (ver a seção seguinte), suponhamos que a congruência cumpre-se para um número composto n. Note-se, então, que n tem um divisor 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ão d divide 1, e se chega a uma contradição.

Usando polinômios

[editar | editar código-fonte]

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

Recordemos que se f(x) é um polinômio não nulo de grau d sobre um corpo F, então f(x) tem um máximo de d raízes em F, 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, sendo g(x)

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

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

O inverso do Teorema de Wilson Diz que para qualquer número composto n > 5,

n divide (n - 1)!.

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

De fato, se q é um fator primo de n, tal que n = qa, os números

1, 2, ..., n - 1

incluindo a - 1 múltiplos de q. Portanto, as potências de q que dividem o fatorial são ao menos n/q - 1; e as potências que dividem n são no máximo

log n/log q.

A inequação:

log n/log q = n/q - 1

É verdade em geral, exceto para o caso q = 2 e n = 4.

Teste de primalidade

[editar | editar código-fonte]

O Teorema de Wilson não se utiliza como teste de primalidade na prática, uma vez que que para calcular (n - 1)! módulo n para um número n 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 primo p:

onde p = 2n + 1. Isto se torna

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

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

  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's Meditationes Algebraicae, Wilson's theorem appears as problem 5 on page 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; see page 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).