Teorema de Wilson

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

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

Prova[editar | editar código-fonte]

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[editar | editar código-fonte]

Tabela de restos módulo n[editar | editar código-fonte]

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[editar | editar código-fonte]

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[editar | editar código-fonte]

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[editar | editar código-fonte]

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.