[obm-l] Re: [obm-l] dúvida!!!

["Cláudio \(Prática\)" <claudio@xxxxxxxxxxxxxxxxxxxxxxx>]

Tem um método que é infalível, apesar de ser também totalmente inútil na
prática: veja se (n-1)! é divisível por n (supondo n > 4). Se for, então n é
composto. Se não for, então n é primo. Isso é consequência do teorema de
Wilson, que diz que n é primo se e somente se n divide (n-1)! + 1.

[]s,
Claudio.

----- Original Message -----
From: <fabio@dias.moreira.nom.br>
To: <obm-l@mat.puc-rio.br>
Sent: Friday, April 09, 2004 10:56 PM
Subject: Re: [obm-l] dúvida!!!


> > como eu posso saber de certeza que certo número não primo? alguma idéia
> > brilhante senhores????
> > [...]
>
> Se n é o tal número, calcule 2^(n-1) (mod n). Se o resultado *não* der 1,
> você tem certeza absoluta de que o número é composto. Por outro lado, se
> der um, você ainda não sabe nada.
>
> Se você ainda estiver desconfiado, você pode tentar calcular 3^(n-1) (mod
> n) -- se der diferente de um, o número é composto. Novamente, se a conta
> der um, isso não quer dizer nada.
>
> Você pode repetir isso quantas vezes você quiser, desde que a base da
> potência não seja um múltiplo de n. A mesma coisa vale: se der diferente
> de um, o número é composto, mas não vale a recíproca. Por exemplo, 2^340 -
> 1 é divisível por 341 = 31*11.
>
> Pior, existem números, como o n = 561 = 51*11 tal que, se mdc(a, n) = 1,
> então a^(n-1) - 1 é divisível por n.
>
> Se você quiser saber mais sobre números primos, o livro "Primos de
> Mersenne (e outros primos muito grandes)" do Nicolau e do Gugu, disponível
> em
>
> http://www.mat.puc-rio.br/~nicolau/publ/publ.html
>
> é um ótimo começo.
>
> []s,
>
> --
> Fábio Dias Moreira
>
>
> =========================================================================
> 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
> =========================================================================

=========================================================================
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
=========================================================================