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