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.
O teorema foi declarado por Ibn al-Haytham (c. 1000 DC), e, no século 18, por John Wilson. Edward Waring anunciou o teorema em 1770, embora nem ele nem seu aluno Wilson pudessem prová-lo. Lagrange deu a primeira prova em 1771. Há evidências de que Leibniz também estava ciente do resultado um século antes, mas nunca o publicou.
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.
| (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 |
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.
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.
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,
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
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
A inequação:
É verdade em geral, exceto para o caso q = 2 e n = 4.
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.