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$ Dec 6, 2016 at 2:26
  • $\begingroup$ So it doesn't hold for all Fibunacci numbers? Or just for all n∈{3,4,5,6}? $\endgroup$ Dec 6, 2016 at 2:42
  • $\begingroup$ BTW $a$ and $b$ will be Fibonacci numbers, too. See, for example, this answer. $\endgroup$ Dec 6, 2016 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, 2016 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$ Dec 13, 2016 at 9:21

2 Answers 2

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