Exatamente! Vejam a minha msg anterior... -- Mensagem original --
>Oi, Yuri: > >O que eu provei foi o seguinte: >m divide n <==> p(x) = x^m - 1 divide q(x) = x^n - 1 >(na verdade, eu provei soh a volta, mas a ida eh imediata) > >Em particular, com um inteiro a fixo: >m divide n <==> p(a) divide q(a). > >Ou seja, eu provei um resultado mais geral do que eu realmente precisava. > >Compare com o seguinte: >2^2 + 1 divide 2^4 + 4 mas nao eh verdade que f(x) = x^2 + 1 divide g(x) >= >x^4 + 4, pois x^4 + 4 = (x^2 + 1)*(x^2 - 1) + 5 > >Um abraco, >Claudio. > >on 16.08.03 12:55, [EMAIL PROTECTED] at [EMAIL PROTECTED] >wrote: > >> >> 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 >========================================================================= > []'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 =========================================================================