(gcd; greatest common divisor) I am pulling a night shift because I have trouble understanding the following task.
Fibonacci is defined by this in our lectures:
I) $F_0 := 1$ and $F_1 := 1$
II) For $n\in\mathbb{N}$, $n \gt 1$ do $F_n=F_{n-1}+F_{n-2}$
Task
Be for n>0 the numbers $F_n$ the Fibonacci-numbers defined as above.
Calculate for $n\in\{3,4,5,6\}$ $\gcd(F_n, F_{n+1})$ and display it as
aFₙ + bFₙ₊₁
, that means find numbers a, b, so that
gcd(Fₙ, Fₙ₊₁) = aFₙ + bFₙ₊₁
holds.
I know how to use the Euclidian Algorithm, but I don't understand from where I should find the a and b from, because the task gives me {3,4,5,6} and every gcd in this gives me 1. (gcd(3,4)=1 ; gcd(4,5)=1) I need help solving this as I am hitting a wall.