[obm-l] Re: [obm-l] Re: [obm-l] Teoria dos Números

[yurigomes@xxxxxxxxxxxxxx]

 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, yurigomes@zipmail.com.br at yurigomes@zipmail.com.br
>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 dudasta@terra.com.br
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
=========================================================================