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.