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: To: 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 =========================================================================r/~nicolau/olimp/obm-l.html =========================================================================
TRANSIRE SVVM PECTVS MVNDOQVE POTIRI
CONGREGATI EX TOTO ORBE MATHEMATICI OB SCRIPTA INSIGNIA TRIBVERE