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

["Eduardo Casagrande Stabel" <dudasta@xxxxxxxxxxxx>]

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

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