- Calcule
, onde
é o
-ésimo número de Fibinacci. Quantas divisões no algoritmo de Euclides precisamos para calcular o MDC?
Passo 1
O enunciado pede calcular
, onde
é a sequência de Fibonacci definida por
,
e
Para isso, usaremos o algoritmo de Euclides, que afirma
Passo 2
Na sequência de Fibonacci temos
e, portanto, o resto da divisão de
por
é
Logo,
Repetindo esse processo sucessivamente, chegamos a
de onde se conclui que
.
Passo 3
Cada aplicação do passo do algoritmo de Euclides faz uma divisão que reduz o par
para
. Começando em
e indo até
, realizamos exatamente
divisões antes de obter resto zero.