Teorema de Wilson

Em matemática, o teorema de Wilson diz que p é um número primo se e somente se:

$(p-1)!\ \equiv \ -1\ ({\mbox{mod}}\ p)$.

Se P é primo então

P divide [(P-1)! + 1].

Todas as n-ésimas diferenças sucessivas da sequência 1^n, 2^n, 3^n, 4^n...

são constantes e iguais a n! (n fatorial).

Resolvendo algebricamente:

2*1 = 1*2^2 - 2*1^2 + 1*0^2

3*2*1 = 1*3^3 - 3*2^3 + 3*1^3 - 1*0^3

4*3*2*1 = 1*4^4 - 4*3^4 + 6*2^4 - 4*1^4 + 1*0^4

5*4*3*2*1 = 1*5^5 - 5*4^5 + 10*3^5 - 10*2^5 + 5*1^5 - 1*0^5

6*5*4*3*2*1 = 1*6^6 - 6*5^6 + 15*4^6 - 20*3^6 + 15*2^6 - 6*1^6 + 1*0^6.

O teorema foi estabelecido por Alhazen e John Wilson.

Prova

Se n é composto mas não é o quadrado de um primo podemos escrever $n=ab$ com $1<a<b<n$. Neste caso tanto $a$ quanto $b$ são fatores de $(n-1)!$ e portanto $(n-1)!\equiv 0{\pmod {n}}$. Se n = $p^{2}$, $p>2$, então $p$ e $2p$ são fatores de $(n-1)!$ e novamente $(n-1)!\equiv 0{\pmod {n}}$ ; isto demonstra que para todo $n\neq 4$ composto temos $(n-1)!\equiv 0{\pmod {n}}$. Se $n$ é primo podemos escrever $(n-1)!\equiv -2*3*...*(n-2){\pmod {n}}$; mas pelo lema anterior podemos juntar os inversos aos pares no produto do lado direito, donde $(n-1)!\equiv -1{\pmod {n}}$.

Exemplos

Tabela de restos módulo n

n	(n-1)!	(n-1)! mod n
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

P=3

2*1 = 1*(2^2-1^2) - 1^2

2*1 + 1^2 = 1*(2^2 - 1^2)

pelo pequeno teorema do Fermat 3 divide (2*1 + 1^2)

P=5

4*3*2*1 = 1*(4^4 - 3^4) - 3*(3^4 - 2^4) + 3*(2^4 - 1^4) - 1^4

4*3*2*1 + 1^4 = 1*(4^4 - 3^4) - 3*(3^4 - 2^4) + 3*(2^4 - 1^4)

pelo pequeno teorema do Fermat 5 divide (4*3*2*1 + 1^4)

P=7

6*5*4*3*2*1 = 1*(6^6-5^6)-5*(5^6-4^6)+10*(4^6-3^6)-10(3^6-2^6)+5(2^6-1^6)-1^6

6*5*4*3*2*1 +1^6 = 1*(6^6-5^6)-5*(5^6-4^6)+10*(4^6-3^6)-10(3^6-2^6)+5(2^6-1^6)

pelo pequeno teorema do Fermat 7 divide (6*5*4*3*2*1 + 1^6)

O interessante é que existe uma crença de que o Teorema de Wilson percebe os pseudo-primos absolutos.

O teorema de Wilson é uma simples variação do Pequeno Teorema do Pierre de Fermat.