[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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




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

[]'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
=========================================================================