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

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

• Part of the confusion here might be that it's not the SAME a, b for every value of $n$; in other words, it's not the case that $\gcd(F_n, F_{n+1})=aF_n+bF_{n+1}$ for all $n$. It might better be written as $\gcd(F_n, F_{n+1})=a_nF_n+b_nF_{n+1}$. – Steven Stadnicki Dec 6 '16 at 2:26
• So it doesn't hold for all Fibunacci numbers? Or just for all n∈{3,4,5,6}? – Andy Velandus Dec 6 '16 at 2:42
• BTW $a$ and $b$ will be Fibonacci numbers, too. See, for example, this answer. – Martin Sleziak Dec 6 '16 at 3:21
• Is it just me or is everyone seeing a bunch of boxes instead of mathematical characters in this question? – Mr. Brooks Dec 6 '16 at 22:32
• That is because your browser doesn't support unicode subscript characters. I should be using the stackoverflow math formatting. I apologize for the inconvinience. – Andy Velandus Dec 13 '16 at 9:21

## 2 Answers

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.

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$$

• and what is a, and what is b in your example? And where does the 4 in F₄ come from? Is it the Index of 5 in the Fibunacci numbers? – Andy Velandus Dec 6 '16 at 2:40
• $a = 2$ and $b=-1$. I'm not sure what your second question is asking. – eepperly16 Dec 6 '16 at 2:43
• The task wants me to this for for every combination 3,4,5,6? (You have done it for 3 and 5, do I also need 3 and 4, 3 and 6 and then 4,5 and 4,6 and so forth?) – Andy Velandus Dec 6 '16 at 3:05
• I believe your task wants you to do this for every pair $F_n, F_{n+1}$ which is different than doing it for every pair in $3,4,5,6$. Or I'm misreading your question. – eepperly16 Dec 6 '16 at 3:08
• Ok, now I am confused. What are the pairs Fₙ, Fₙ₊₁? – Andy Velandus Dec 6 '16 at 3:18