Deixem eu me corrigir! Se eu descobrir um outro erro, deixarei que outros me corrijam, para eu não entrar num loop de auto-correções. A resposta que o Cláudio deu está certa, vou explicar o porquê. Na verdade, não se precisa usar polinômios na solução.
Segundo o que o Cláudio - pelo teorema de Euler - escreveu p(a) = a^n - 1 divide q(a) = a^Phi(a^n - 1) - 1. Suponhamos que n não divide Phi(a^n - 1), então Phi(a^n - 1) = qn + r sendo 0 < r < n Daí q(a) = a^(qn + r) - 1 = a^r * a^(qn) - a^r + a^r - 1 = a^r * (a^(qn) - 1) + (a^r - 1) É claro que p(a) = a^n - 1 divide a^(qn) - 1, portanto a^n - 1 deve dividir a^r - 1, só que este último número é menor do que a^n - 1, uma contradição. Obrigado! Duda. From: "Eduardo Casagrande Stabel" <[EMAIL PROTECTED]> > Oi Yuri. > > Eu acho que você tem razão. > > Fixando n, nós temos duas expressões > > p(a) = a^n - 1 > > q(a) = a^Phi(a^n - 1) - 1 > > A primeira é um polinômio de grau n, a segunda não tem cara de ser um > polinômio (de fato, fazendo a crescer, ela cresce na forma a^a, que é muito > mais veloz do que um polinômio, portanto não pode ser um polinômio). O > Dirichlet intuiu que nós podemos chegar a uma expressão relação do tipo > t^n-1 | t^(fi(a^n-1))-1, mas não sei como se chegaria a isso. O caminho que > o Cláudio usou - utilizando o teorema de Euler - colocará o t dentro do > expoente que tem o Phi. > > Acho que ainda está por resolver. > > Duda. > > From: <[EMAIL PROTECTED]> > > > > 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 > > ========================================================================= > > > > > > ========================================================================= > 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 =========================================================================