Re: Problema

["Ecass Dodebel" <ecassdodebel@xxxxxxxxxxx>]

>From: "Ecass Dodebel" <ecassdodebel@hotmail.com>
>Reply-To: obm-l@mat.puc-rio.br
>To: obm-l@mat.puc-rio.br
>Subject: Problema
>Date: Sat, 22 Jul 2000 21:19:00 GMT
>
>Oi!
>
>Problema.
>Dados a,n naturais, não nulos. A sequencia x[k] é definida por x[0]=a, e 
>x[k+1]=a^x[k]. Provar que existe N tal que todo o k>N satisfaz 
>x[k]=x[k+1](mod n).
>
>Obrigado!
>
>Eduardo Casagrande Stabel.
>________________________________________________________________________
>Get Your Private, Free E-mail from MSN Hotmail at http://www.hotmail.com
>

Minha solução é a seguinte:
Fato1.
x[k]=x[k+1](mod n), similar a
a^x[k-1]=a^x[k](mod n), se e somente se
x[k-1]=x[k](mod ord_a(n))
mas ord_a(n)<=phy(n)<n

Agora é só provar por indução completa.
- x[k]=x[k+1](mod n) para k>N, para n=1
- se x[k]=x[k+1](mod n), para k>N, valer pra n=1,...,q vale para q+1.
Prova. o enunciado vale para n=q+1 se e somente se vale para 
n=ord_a(q+1)<q+1 (pelo fato1), o que é verdade pela hipótese de indução.
- daí vale para qualquer n...

PS. ord_a(n) é o menor natural t tal que a^t=1(mod n), ou seja, n divide 
a^t-1

PS2. eu li esse problema, pela primeira vez, no começo do ano passado (eu 
estava no segundo ano do segundo grau). Desde quando eu li, venho tentando 
resolvê-lo, e só agora consegui uma solução, que não tenho certeza se está 
correta. Por favor, comentem!

Muito Obrigado!

Eduardo Casagrande Stabel.

________________________________________________________________________
Get Your Private, Free E-mail from MSN Hotmail at http://www.hotmail.com