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

Passo 1

Estamos com os números de Fibonacci definidos por F₁=F₂=1 e Fₙ=F_{n-1}+F_{n-2}, e queremos mostrar que o máximo divisor comum de Fₙ e F_{n+1} é 1. Para isso vamos usar propriedade do Algoritmo de Euclides e indução.

Passo 2

A relação de recorrência dos Fibonacci e a propriedade do Algoritmo de Euclides que vamos usar são:
Fn+1=Fn+Fn-1,
e
mdc(a,b)=mdcl(b,,abmod br)

Passo 3

Aplicando o Algoritmo de Euclides em mdc(Fn,,Fn+1), temos:
mdc(Fn,,Fn+1)=mdcl(Fn,,Fn+1bmod Fnr)
Como Fn+1=Fn+Fn-1, o resto de Fn+1 na divisão por Fn é precisamente Fn-1. Logo
mdc(Fn,,Fn+1)=mdc(Fn,,Fn-1)

Passo 4

Repetindo esse mesmo passo sucessivamente, vamos reduzindo o par de argumentos do mdc até chegarmos em
mdc(F2,,F1)

Passo 5

Como F1=1 e F2=1, temos
mdc(F2,,F1)=mdc(1,1)=1
Portanto, por indução reversa pelo Algoritmo de Euclides, obtemos mdc(Fn, Fn+1)=1 para todo n.

Resposta

(Fn, Fn+1) = 1

Exercícios relacionados