Mostrar que para os números de Fibonacci, definidos no problema anterior, satisfazem
(Fn, Fn+3)=1 ou 2 .

Passo 1

O enunciado pede para mostrar que, dados os números de Fibonacci definidos por
F1=1,;F2=1, Fn+2=Fn+1+Fn,
temos
gcdl(Fn,,Fn+3r);=;1 ou 2
Vamos usar o algoritmo de Euclides para o cálculo de máximo divisor comum e observar a paridade dos Fn.

Passo 2

Pelo algoritmo de Euclides,
gcdl(Fn,,Fn+3r) =gcdl(Fn,;Fn+3-2,Fn+1r)
Como
Fn+3=Fn+2+Fn+1=(Fn+1+Fn)+Fn+1=2,Fn+1+Fn,
segue-se
gcdl(Fn,,Fn+3r) =gcdl(Fn,,2,Fn+1r)

Passo 3

É fato clássico que dois termos consecutivos de Fibonacci são primos entre si, ou seja
gcdl(Fn,,Fn+1r)=1
Então todo divisor comum de Fn e de 2,Fn+1 deve dividir Fn e também dividir 2, pois não pode “vir” de Fn+1. Logo
gcdl(Fn,,2,Fn+1r) =gcdl(Fn,,2r),
que só pode valer 1 ou 2.

Passo 4

Resta ver quando 2 divide Fn. Observa-se que a sequência l(Fnbmod2r) é periódica de período 3:
F1equiv1,;F2equiv1,;F3equiv0,;F4equiv1,;F5equiv1,;F6equiv0,;dots
Portanto Fn é par se, e somente se, n for múltiplo de 3. Logo
gcdl(Fn,,2r)= 2,&3mid n, 1,&3nmid n

Resposta

gcdl(Fn,,Fn+3r) vale 2 se 3mid n e vale 1 caso contrário. Em todo caso é 1 ou 2.

Exercícios relacionados