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)² = 1 (mod p), tem-se que (a · a)² = (-1)² = 1 (mod p). Pode-se deduzir, então, que a² tem inverso multiplicativo no módulo p, o qual não pode ser verdadeiro pois mcd(a², 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² = 1 (mod p), que se pode fatorar em a² - 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.

Ver também

• Aritmética modular
• Teorema de Euler
• Pequeno Teorema de Fermat