Fibonacci

["Eric Campos" <mathfire@xxxxxxxxxx>]

O seguinte problema foi proposto por Jose Paulo Carneiro

As duas sequencias:
1, 1, 2, 3, 5, 8, 13, ...
e
1, 3, 4, 7, 11, ...

Sao ambas tais que cada termo eh a soma dos dois anteriores.
Observacoes: a segunda sequencia eh chamada "sequencia de Lucas".

Mostre que:

dado um inteiro positivo arbitrario m, existe sempre algum termo da
primeira sequencia que eh multiplo de m.

Imaginei uma solucao assim:

seja f(i) o i-esimo termo da sucessao de Fibonacci 1, 1, 2, 3, 5, 8, 13,
..., em que cada termo eh a soma dos dois anteriores. Seja m um inteiro
generico. Considere a funcao g(n) = resto de f(n) quando dividido por m, com
g(n) nao negativo. Eh claro que g eh uma sucessao, pois g esta definida no
conjunto dos naturais. Como ha no maximo m distintos valores possiveis para
g(n), ha no maximo m^2 distintos possiveis pares de inteiros consecutivos na
sucessao g. Portanto existem inteiros positivos i,k para os quais
(g(i),g(i+1)) = (g(i+k),g(i+k+1)), isto eh, existem dois pares de numeros de
Fibonacci consecutivos que tem o mesmo resto (positivo) na divisao por m.
Nesse caso como g(i) + g(i+1) = g(i+k) + g(i+k+1) temos em particular que
g(i+2) = g(i+k+2), e de modo mais geral g(n) = g(n + k) para cada n inteiro
positivo. logo 1 = g(1) = g(1 + k) e 1 = g(2) = g(2 + k), donde g(k) = g(2 +
k) - g(1 + k) = 0, isto eh, m divide f(k).

Eric.