Muito bom!! abraços, Salhab
2009/9/30 Bernardo Freitas Paulo da Costa <bernardo...@gmail.com> > 2009/9/30 Lucas Colucci <lucascolu...@hotmail.com>: > > 04. Mostrar que 47| (2^23 - 1) > > 2^10=1024==37 (mód 47) => 2^20==37^2=(-10)^2==100==6 (mód 47) > > Daí, 2^23==6*2^3==48==1 (mód 47) > > => 2^23-1==0 (mód 47), e o resultado segue. > Bom, funciona, mas essa questão é típica de ligar o desconfiômetro do > nosso aluno olímpico, não ? Enfim, duas coisas importantes: se você > sabe um jeito de fazer, mesmo que demore um bom tempo, faça. Segundo, > quando você vir alguma coisa mágica, ligue o desconfiômetro por um > tempo, tente, e se você não conseguir, volte ao método "força bruta". > Aqui, o desconfiômetro liga bem rápido, porque 23 = 46/2, e pelo > pequeno teorema de Fermat (como 47 é primo), x^46 == 1 mod 47 para x > primo com 47. Portanto, basta provar que 2 é um quadrado, tipo x^2 == > 2 mod 47 e daí 2^23 == x^46 == 1. Mas 47+2 = 49 = 7^2, e acabou. > Aliás, como dever de casa para o Diogo, prove que 47 | (y^23 - 1) é > estritamente equivalente a y == x^2 para algum x. E depois disso, > estude resíduos quadráticos, e a fórmula de Lagrange, que têm tudo a > ver com esta questão. > > -- > Bernardo Freitas Paulo da Costa > > ========================================================================= > Instruções para entrar na lista, sair da lista e usar a lista em > http://www.mat.puc-rio.br/~obmlistas/obm-l.html<http://www.mat.puc-rio.br/%7Eobmlistas/obm-l.html> > ========================================================================= >
