Find numbers a, b, so that gcd(Fₙ, Fₙ₊₁) = aFₙ + bFₙ₊₁ holds using Euclidean Algorithm

Question

(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.

Answer 1

Here you want to replace $a$ and $b$ with $a_n$ and $b_n$. We have $$a_nF_{n} + b_n F_{n+1}=gcd(F_n, F_{n+1}) =gcd(F_{n-1}, F_n)=a_{n-1}F_{n-1}+ b_{n-1}F_n$$

Replace $F_{n+1}$ with $F_n+F_{n-1}$, we get $$(a_n + b_n - b_{n-1})F_n + (b_n-a_{n-1})F_{n-1}=0$$

If we let $a_n + b_n - b_{n-1}=0$ and $ b_n-a_{n-1}=0$, we could get an $F-$ sequence again. For example, replace $a_n$ in the first equation with $b_{n+1}$ and let $c_n=(-1)^nb_n$, we get $$c_{n+1}=c_n+c_{n-1}$$

We can let $b_0=1$ and $b_1=-1=a_0$, then it can be shown $c_n=F_{n+1}$ (assume $F_0=0$, $F_1=1$) and thus $$b_n=(-1)^{n}F_{n+1}$$ and $$a_n = (-1)^{n+1} F_{n+2}$$, And we are looking at a famous identity $$F_{n+1}^2-F_nF_{n+2} = (-1)^{n}gcd(F_n, F_{n+1})=(-1)^{n}$$

Hope you feel this is interesting.

Answer 2

What you need here is the so-called Extended Euclidean Algorithm where you back substitute to calculate numbers $a$ and $b$ such that $aF_n + bF_{n+1} = \gcd(F_n,F_{n+1})$. For example, let's use $F_3 = 3$ and $F_4 = 5$, Then

$$ 5 = 1\cdot3 + 2 $$ $$ 3 = 1\cdot2 + 1 $$

Rearranging and substituting gives

$$ 2 = 5 - 3 $$ $$ 3 = (5 - 3) + 1$$

Which gives

$$ 2\cdot 3 - 5 = 1$$

That is

$$ 2F_{3} + (-1) F_4 = 1$$