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

[<fabio@xxxxxxxxxxxxxxxxxxx>]

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