0
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ 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}$. $\endgroup$ – Steven Stadnicki Dec 6 '16 at 2:26
  • $\begingroup$ So it doesn't hold for all Fibunacci numbers? Or just for all n∈{3,4,5,6}? $\endgroup$ – Andy Velandus Dec 6 '16 at 2:42
  • $\begingroup$ BTW $a$ and $b$ will be Fibonacci numbers, too. See, for example, this answer. $\endgroup$ – Martin Sleziak Dec 6 '16 at 3:21
  • $\begingroup$ Is it just me or is everyone seeing a bunch of boxes instead of mathematical characters in this question? $\endgroup$ – Mr. Brooks Dec 6 '16 at 22:32
  • $\begingroup$ That is because your browser doesn't support unicode subscript characters. I should be using the stackoverflow math formatting. I apologize for the inconvinience. $\endgroup$ – Andy Velandus Dec 13 '16 at 9:21
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
7
  • $\begingroup$ 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? $\endgroup$ – Andy Velandus Dec 6 '16 at 2:40
  • $\begingroup$ $a = 2$ and $b=-1$. I'm not sure what your second question is asking. $\endgroup$ – eepperly16 Dec 6 '16 at 2:43
  • $\begingroup$ 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?) $\endgroup$ – Andy Velandus Dec 6 '16 at 3:05
  • $\begingroup$ 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. $\endgroup$ – eepperly16 Dec 6 '16 at 3:08
  • $\begingroup$ Ok, now I am confused. What are the pairs Fₙ, Fₙ₊₁? $\endgroup$ – Andy Velandus Dec 6 '16 at 3:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.