1. Calcule \operatorname{mdc}\left\{F_{n}, F_{n+1}\right\}, onde F_{n} é o n-ésimo número de Fibinacci. Quantas divisões no algoritmo de Euclides precisamos para calcular o MDC?

Passo 1

O enunciado pede calcular \gcd(F_n, F_{n+1}), onde (F_k) é a sequência de Fibonacci definida por F_0=0, F_1=1 e
F_{k+1}=F_k+F_{k-1}.
Para isso, usaremos o algoritmo de Euclides, que afirma
\gcd(a,b)=\gcd\bigl(b,\,a \bmod b\bigr).

Passo 2

Na sequência de Fibonacci temos
F_{n+1}=F_n+F_{n-1}
e, portanto, o resto da divisão de F_{n+1} por F_n é
F_{n+1}\bmod F_n=F_{n-1}.
Logo,
\gcd(F_{n+1},F_n) =\gcd\bigl(F_n,\,F_{n+1}\bmod F_n\bigr) =\gcd(F_n,F_{n-1}).
Repetindo esse processo sucessivamente, chegamos a
\gcd(F_2,F_1)=\gcd(1,1)=1,
de onde se conclui que \gcd(F_n,F_{n+1})=1.

Passo 3

Cada aplicação do passo do algoritmo de Euclides faz uma divisão que reduz o par (F_{k+1},F_k) para (F_k,F_{k-1}). Começando em k=n e indo até k=1, realizamos exatamente n divisões antes de obter resto zero.

Resposta

\gcd(F_n,F_{n+1})=1 e são necessárias n divisões no algoritmo de Euclides.

Exercícios relacionados