# Teorema de Wilson

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 $(n-1)!=1\times 2\times 3\times \cdots \times (n-1)$ satisfaz
    $(n-1)!\ \equiv \;-1{\pmod {n}}$
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.

## História

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.

## Exemplos

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 :
| $n$ | $(n-1)!$ (sequência A000142 na OEIS) | $(n-1)!\ {\bmod {\ }}n$ (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 |

## Provas
### Usando aritmética modular

Por contradição, suponha que, para um número p ≥ 2, que não é primo, cumpre-se a expressão:
    $(p-1)!\equiv -1{\pmod {p}}$
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
    $a\cdot \alpha \equiv -1{\pmod {p}}$
sendo
    $\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 (mod p), tem-se que (a · a)$^2$ = (-1)$^2$ = 1 (mod p). Pode-se deduzir, então, que a$^2$ tem inverso multiplicativo no módulo p, o qual não pode ser verdadeiro pois mcd(a$^2$, p) ≠ 1, de maneira que a suposição inicial de que p não é primo, é falsa.

### Usando teoria de grupos

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 a$^2$ = 1 (mod p), que se pode fatorar em a$^2$ - 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:
    $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 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

Seja p um número primo. Consideremos o polinômio:
    $g(x):=(x-1)(x-2)\cdots (x-(p-1)).\,$
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)
    $f(x):=g(x)-(x^{p-1}-1).\,$
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.

## Recíproca

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

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:
    $1\cdot 2\cdots (p-1)\ \equiv \ -1\ ({\mbox{mod}}\ p)$
    $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)$
onde p = 2n + 1. Isto se torna
    $\prod _{j=1}^{n}\ j^{2}\ \equiv (-1)^{n+1}\ ({\mbox{mod}}\ p).$
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:
    $\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.