[obm-l] Re: [obm-l] Tá pegando...

["Eric Campos Bastos Guedes" <mathfire@xxxxxxxxx>]

> "Prove que n é primo se, e somente se, (n-1)!=-1 (mod n).
>
> Este eh o Teorema de Wilson. Em qualquer livro de Teoria dos Numeros voce
o encontra.Ou na internet.

Uma prova que conheço é assim:

Inicialmente lembremos o pequeno teorema de Fermat:

"Se p eh primo e p nao divide a entao a^(p-1) == 1 mod p"

agora suponha n=p primo. Considere

[1]     X^(n-1) == 1 mod n

conforme o pequeno teorema de Fermat, a equação [1] acima
tem as soluções X=1,2,3,...,n-1, isto eh se

[2]     f(X) = X^(n-1) -1

entao f(X) tem as raizes 1,2,3,...,n-1 modulo n, e portanto podemos
fatorar f(X) = X^(n-1)-1 assim:

f(X) = X^(n-1) - 1 = (X-1)(X-2)(X-3)...(X-(n-1)) mod n

igualando os termos independentes de X^(n-1) - 1 e de
(X-1)(X-2)(X-3)...(X-(n-1)) obtemos

-1 == (-1)(-2)(-3)...(-(n-1)) mod n

isto eh

[3]       -1 == (n-1)!(-1)^(n-1) mod n

se n eh primo impar tem-se (-1)^(n-1) = 1 e portanto [3] fornece

(n-1)! == -1 mod n

se n=2 tem-se (n-1)!=(2-1)!=1== 1 == -1 mod 2, isto eh

(n-1)! == -1 mod n

de qualquer forma

(n-1)! == -1 mod n

Abrac,os,

---------------------------------------------
Eric Campos Bastos Guedes
mathfire@ig.com.br
Confira o livro:
"Formulas que geram numeros primos" no site
www.primeformulas.hpg.com.br

=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
O administrador desta lista é <nicolau@mat.puc-rio.br>
=========================================================================