Opa! Na verdade vale uma coisa mais geral! a^n- 1 divide a^m- 1 <=> n divide m. Dessa forma, tirei a minha dúvida. Além disso, a prova do Cláudio prova também a afirmação acima. Ateh mais, Yuri -- Mensagem original --
> >Oi Claudio, > >Eu não entendi pq vc considerou polinômios para provar a última passagem, >jah que a está fixo. Ou seja, vc tem que >a^n - 1 divide a^Phi(a^n - 1) - 1 > e não que x^n-1 divide x^Phi(a^n - 1) - 1 para todo x. > Se eu tiver falado alguma besteira, me avisem! > Ateh mais, > Yuri >-- Mensagem original -- > >>on 16.08.03 05:54, Eduardo Casagrande Stabel at [EMAIL PROTECTED] wrote: >> >>> Olá pessoal! >>> >>> Prove que se n > 1 e a > 0 são inteiros então n | PHY(a^n - 1). >>> >>> PHY é a função de Euler. >>> >>> Abraço, >>> Duda. >>> >> >>Oi, Duda: >> >>Eh claro que mdc(a,a^n - 1) = 1 >> >>Entao, pelo teorema de Euler, teremos: >>a^Phi(a^n - 1) == 1 (mod a^n - 1) ==> >> >>a^n - 1 divide a^Phi(a^n - 1) - 1 ==> >> >>n divide Phi(a^n - 1) >> >>*** >> >>Essa ultima passagem pode ser vista da seguinte forma: >> >>Sejam x^n - 1 e x^n - 1 polinomios (portanto m, n inteiros) >> >>x^n - 1 divide x^m - 1 mas n nao divide m ==> >> >>m = qn + r com 0 < r <= n-1 ==> >> >>x^m - 1 = x^(qn + r) - 1 = x^(qn)*x^r - x^r + x^r - 1 = >>= x^r(x^(qn) - 1) + x^r - 1 ==> >> >>x^n - 1 divide x^r - 1 com 0 < r < n ==> >> >>contradicao. >> >> >>Um abraco, >>Claudio. >> >>========================================================================= >>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 >>========================================================================= >> > >[]'s, Yuri >ICQ: 64992515 > > >------------------------------------------ >Use o melhor sistema de busca da Internet >Radar UOL - http://www.radaruol.com.br > > > >========================================================================= >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 >========================================================================= > []'s, Yuri ICQ: 64992515 ------------------------------------------ Use o melhor sistema de busca da Internet Radar UOL - http://www.radaruol.com.br ========================================================================= 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 =========================================================================