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

[obm-l] Re: [obm-l] Algum_progresso_(seq��ncia_de_pot�ncias)



Acho que vc n�o leu a mensagem mais recente onde eu mostro que isso com certeza acontece para um algum n.
 
Na verdade eu acho que j� d� pra generalizar a demonstra��o, por enquanto estou sem tempo, mas depois eu formalizo melhor a solu��o completa (acho que d�!) para o problema.
----- Original Message -----
Sent: Wednesday, February 26, 2003 1:19 PM
Subject: Re: [obm-l] Algum_progresso_(seq��ncia_de_pot�ncias)

Como voce garante que a^^n==a^^(n+1) modulo 1000 sem ter demonstrado isso?Nada te garante isso inicialmente.

 "Domingos Jr." <dopikas@uol.com.br> wrote:

Para o problema:
seja A(1) = a e A(n + 1) = a^A(n) para n >= 1, provar que para todo inteiro
a > 1 os �ltimos 1000 d�gitos da s�rie A(1), A(2), ... eventualmente se
mant�m fixos.

seja a tal que mdc(a, 10) = 1 => mdc(a, 10^n) = 1 para todo n >= 0
sendo phi a fun��o de Euler, phi(10^n) = 4.10^(n-1)

suponha que exista um inteiro n tal que A(n) = A(n + 1) (mod 10^1002)
A(n+1) = q.10^1002 + A(n) para algum q inteiro
A(n+2) = a^A(n+1) = a^[q.10^1002 + A(n)]
mas phi(10^1001) = 4*10^1000 e 10^1002 � um m�ltiplo desse n�mero, logo pelo
teorema de Euler, temos que a^(10^1002.q) = [a^(10^1002)]^q = 1^q = 1 (mod
10^1001)
portanto:

(1) A(n+2) = 1.a^A(n) = A(n+1) (mod 10^1001)

temos tamb�m que:
A(n+2) = [a^(10^1002q)] * A(n+1)
se q � par phi(10^1002) divide 10^1002q e logo A(n+2) = A(n+1) (mod 10^1002)

logo, se A(n+2) != A! (n+1) (mod 10^1002) temos que ter q = 2k + 1 para algum
k, logo:
A(n+2) = [a^(10^1002)] * A(n+1) (mod 10^1002)
elevando ambos ao quadrado, temos
A(n+2)� = [a^(10^1002)]� * A(n+1)� (mod 10^1002)
A(n+2)� = A(n+1)� (mod 10^1002)
onde sa�: A(n+2) = A(n+1) ou A(n+2) + A(n+1) = 0 (mod 10^1002)
essa conta pode ser feita pois como mdc(a, 10^2002) = 1 as pot�ncias de a
pertencem a um grupo multiplicativo mod 10^2002.

nos interessa analisar o caso A(n+2) + A(n+1) = 0, como vimos no item (1),
os �ltimos 1001 d�gitos de A(n+2) e A(n+1) s�o iguais, sendo assim:

se A(n+2) = A(n+1) = x (mod 10^1001) com x < 10^1001, e u, v forem os 1002�
d�gitos de A(n+2) e A(n+1) respectivamente, temos:

(u + v)*10^1001 + 2x = 0 (mod 10^1002)
ou seja, existe um m tal que:
(u + v)*10^1001 + 2x = m.10^1002
2x = 10^1001*(10m - u - v)
(2) .... x = 5^1001*(10m - u - v)

ops! x = 0 (mod 10^1000) :-) sendo assim eu n�o preciso fazer mais nada, ! os
pr�ximos termos da seq��ncia com certeza ter�o os 1000 �ltimos d�gitos todos
zeros!!!

de (1) e (2) temos que a seq��ncia vai repetir os �ltimos 1002 d�gitos
sempre a partir de n ou ent�o � garantido que os �ltimos 1000 d�gitos
fixam-se em 0.

Para o caso mdc(a, 10) = 1, basta ent�o provarmos que existe n tal que
A(n+1) = A(n) (mod 10^1002) teremos provado que os 1000 �ltimos d�gitos
eventualmente s�o fixados...

Ser� que s� eu estou me "divertindo"? Ou as demonstra��es est�o confusas
demais?

[ ]'s

=========================================================================
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
O administrador desta lista �
=========================================================================



Busca Yahoo!
O servi�o de busca mais completo da Internet. O que voc� pensar o Yahoo! encontra.