[obm-l] Re: [obm-l] Re:_[obm-l]_ajuda_com_desigualdade(outra_soluçao)

["Cláudio \(Prática\)" <claudio@xxxxxxxxxxxxxxxxxxxxxxx>]

> > 8°) Mostre que existe um número inteiro positivo na
> > seqüência de Fibonacci que é divisível por 1000.
>
> Esse ai eu calculei na mão (bem, usei o computador) e
> descobri que todos os F(n*750), para n natural, onde
> F(n) é o n-ésimo número da sequencia com F(0) = 0 e
> F(1) = 1 são divisíveis por 1000.
> Só falta provar :P
>
Esse é um caso particular da seguinte propriedade geral dos números de
Fibonacci:
"A sequencia de Fibonacci é periódica (mod n) para todo inteiro n >= 2"

Para provar este fato, considere os pares ordenados (F(k),F(k+1)) k >= 0.
Modulo n, existem no máximo n^2 pares ordenados distintos com coordenadas
inteiras.
Assim, devem existir inteiros não-negativos r e s tais que r < s e:
 (F(r),F(r+1)) == (F(s),F(s+1))  (mod n) ==>

F(s+1) == F(r+1) (mod n)  e  F(s) == F(r) (mod n)

Usando a equação de recorrência que define a sequencia de Fibonacci e
indução, chegamos à conclusão de que:
F(0) == F(s-r) (mod n)   e   F(1) == F(s-r+1) (mod n)

Tomando n = 1000 e levando em conta que F(0) = 0 é divisível por 1000,
concluímos que existe um inteiro positivo k tal que:
F(0) == F(k) == F(2k) == ... == 0 (mod n).
(por exemplo, k = 750, como determinou o Helder)

De fato, acabamos provando um resultado mais forte: existem infinitos termos
da sequencia de Fibonacci que são divisíveis por 1000.

Um abraço,
Claudio.

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