Re: [obm-l] congruência

["Johann Peter Gustav Lejeune Dirichlet" <peterdirichlet2003@xxxxxxxxx>]

Bem, apenas mais um comentário meio que filosófico sobre a soluçao do colega:

Qualquer pessoa que chegue e veja isso, sem conhecer a história de tal prova, pensa coisas do tipo "Nossa! Como será que ele fez isso?" ou "Eu nunca vou conseguir pensar nisto na hora da prova..." e coisas assim... Por isso mesmo, vou falar um pouco de como Euler produziu esta pequena jóia (pode ser pura mandracaria agora, mas quase ninguém nega que esta tem lugar reservado no "O Livro"). Para tal, esteja com o seguinte material em mãos:
-- Primos de Mersenne (e outros primos muito grandes), disponível nas páginas pessoais do Gugu e do Nicolau.
-- Eureka! 2, disponível na página da OBM.
Só vou aterrorizar, digo, avisar de que a leitura dos dois acima demanda um tempinho e muito boa vontade de quem se aventura a tal, mas não deixa de ser interessante...

Bem, é fato que os primos da forma 2^n+1 sao da forma F(n)=2^2^n+1=pow(2,pow(2,n))+1 
(aqui, potenciacao é a operacao de maior precedencia e a associatividade é pela esquerda).
Então, seria bom saber como são os fatores primos de F(n).
Bem, se p (primo por SP) divide F(n), temos

2^(2^n) = -1 (mod p)
Assim

2^(p-1) = +1  (mod p) (Euler-Fermat)
2^(2^(n+1)) = 1 (mod p) 
Se g é o menor tal que
2^g = +1  (mod p)
temos que
g divide p-1,
g divide 2^(n+1)
mas g nâo divide 2^n
Logo g=2^n, e 2^n divide p-1
Assim p=k*2^n+1
Logo temos um teoreminha bastante interessante...

"Os fatores primos de F(n) são da forma k*2^n+1". (nao tenho certeza mas creio que dá pra melhorar tal teorema...)

No nosso caso, F(5), temos que testar caras da forma k*2^5+1=32k+1 que sejam menores que sqrt(F(5)).
Fazendo algumas contas na raça, vemos que o melhor ajuste é 641, com k=20.

Uma pergunta que muita gente um pouco mais curiosa se faz é "Mas como Fermat tinha uma esperança tão grande de que tais números fossem realmente primos, sendo que o problema até hoje falhou espetacularmente?", ou "Como ele se expôs a uma gafe dessas?" Bem, a minha resposta fica para outra hora :P

Em 15/10/06, Carlos Eddy Esaguy Nehab <carlos@nehab.net> escreveu:

Oi,  Leandro,

Não custa lembrar qual o contexto original da questão postada, pois esta questão, particularmente não veio do nada...

Primos de Fermat

Um número é primo de Fermat se é primo e é da forma  2^n + 1.    É simples perceber que se N é primo de Fermat, o expoente n deve ser potência de 2.    Assim, para k = 0 a 4, N = 2^(2^k) + 1 são de fato primos (3, 5, 17, 257 e 65.537), mas Fermat havia conjecturado que qq cara da forma 2^(2^k) + 1 era primo, o que se mostrou não ser verdade para k = 5, que é exatamente o problema que você propôs (e cuja solução, clássica, já foi postada).

Nehab


At 12:44 15/10/2006, you wrote:

Demonstre que (2^32)+1 é divisível por 641

-- 
Ideas are bulletproof.

V