[obm-l] Algum progresso (seqüência de potências)

["Domingos Jr." <dopikas@xxxxxxxxxx>]

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 é <nicolau@mat.puc-rio.br>
=========================================================================