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

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

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

Acho que consegui fechar a prova para o caso mdc(a, 10) = 1.

defina g(n) = A(n+1) - A(n), n >= 1
manipulando g(n):
g(n) = a^A(n) - a^A(n-1) = a^A(n-1)*[a^(A(n) - A(n-1)) - 1] =
A(n)[a^g(n-1) - 1]

para que g(n) = 0 (mod 10^1002) temos que a^g(n-1) = 1 (mod 10^1002)
para isso basta (aqui não é se e somente se!) que g(n-1) = 0 (mod
phi(10^1002) = 4.10^1001)
ou seja a^g(n-2) = 1 (mod 4.10^1001)
seguindo essa linha de raciocínio, podemos continuar até chegarmos em:
a^g(n-1002) = 1 (mod 2^2004)
como phi(2^n) = 2^(n-1) podemos ir voltando atrás até chegarmos ao simples:
a^g(n-3005) = 1 (mod 2)

mas isso é verdade pois 2 não divide a, logo uma potência de a é ímpar!
a demonstração segue no sentido contrário!

Falta agora apenas o caso 2|a e 5|a :-)

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