Find $\gcd(f_{n+1}, f_{n+2})$ by using Euclidean algorithm for the Fibonacci numbers whenever $n>1$. How many division algorithms are needed? (Recall that the Fibonacci sequence $(f_n)$ is defined by setting $f_1=f_2=1$ and $f_{n+2}=f_{n+1}+f_n$ for all $n \in \mathbb N^*$, and look here to get information about Euclidean algorithm)
[Math] How to find $\gcd(f_{n+1}, f_{n+2})$ by using Euclidean algorithm for the Fibonacci numbers whenever $n>1$
elementary-number-theory
Related Solutions
Step 1. Since, by the Binet formula, $$ F_n = \frac{1}{\sqrt{5}}\left(\sigma^n-\bar{\sigma}^n\right), $$ where $\sigma+\bar{\sigma}=1$ and $\sigma\bar{\sigma}=-1$, we have: $$ F_m \mid F_{mn}, $$ since in $\mathbb{Z}[x,y]$ the polynomial $x^m-y^m$ divides the polynomial $x^{mn}-y^{mn}$.
Step 2. We can prove our statement by assuming without loss of generality that $k$ is a prime power. The Chinese theorem in conjunction with Step 1 grants that if the statement holds when $k$ is a prime power, then it holds for every integer.
Step 3. The Pisano period for the Fibonacci and Lucas sequences $\!\!\pmod{2}$ is $3$. In particular, $F_n$ (as well as $L_n$) is even iff $n$ is a multiple of $3$. Moreover, $$ F_{2n} = F_n \cdot L_n.$$
Step 4. By assuming that $2^h\mid F_n$ we have $n=3m$ in virtue of Step 3, and: $$ F_{2^{(d-1)h}n} = F_{2^{(d-1)h}3m} = F_{2^{(d-1)h-1}3m}L_{2^{(d-1)h-1}3m} = F_{3m}\cdot\prod_{j=0}^{(d-1)h-1}L_{3\cdot 2^j m}, $$ so: $$ \nu_2(F_{2^{(d-1)h}n})\geq \nu_2(F_{n}) + (d-1)h \geq dh,$$ since every term in the product is even. So we just proved the statement in case that $k$ is a power of $2$.
Step 5. We assume now that $k$ is odd. Since $\frac{x^l-y^l}{x-y}=\sum_{j=0}^{l-1} x^j y^{l-1-j}$, we have: $$\frac{F_{kn}}{F_n}=\sum_{j=0}^{k-1} \sigma^{jn}\bar{\sigma}^{(k-1-j)n}=(-1)^{\frac{k-1}{2}n}+\sum_{j=0}^{\frac{k-1}{2}} (-1)^{jn} L_{(k-1-2j)n},$$ where $L_a = \sigma^a + \bar{\sigma}^a$. If now we use the identity: $$ L_{2a} = \sigma^{2a}+\bar{\sigma}^{2a} = 5 F_a^2 + 2(-1)^a$$ we get: $$\frac{F_{kn}}{F_n}= (-1)^{\frac{k-1}{2}n}+\sum_{j=0}^{\frac{k-1}{2}} (-1)^{jn}\left(5 F_{\left(\frac{k-1}{2}-j\right)n}^2+2(-1)^{\left(\frac{k-1}{2}-j\right)n}\right).$$ Since $F_n$ divides $F_{mn}$ and $k$ divides $F_{n}$, the last sum $\pmod{k}$ is just: $$ \frac{F_{kn}}{F_n}\equiv (-1)^{\frac{k-1}{2}n}+\sum_{j=0}^{\frac{k-1}{2}}2(-1)^{\frac{k-1}{2}n}\equiv k (-1)^{\frac{k-1}{2}n}\equiv 0\pmod{k}.$$ Hence we have that $k\mid F_n$ implies $(k F_n)\mid F_{kn}$, and our claim follows by induction.
The number of steps required to compute $\gcd(a,b)$ is given by the length$^{(*)}$ of the continued fraction of $\frac{a}{b}$. It follows that the worst-case scenario for the Euclidean algorithm is given by the convergents of $\varphi=\frac{1+\sqrt{5}}{2}=[1;1,1,1,1,\ldots]$, i.e. by consecutive Fibonacci numbers.
(*) Explanation: assuming $a>b$, a step of the Euclidean algorithm brings the couple $(a,b)$ into the couple $(b,a\pmod{b})$. On the other hand, the Gauss map $x\mapsto \frac{1}{x-\lfloor x\rfloor}$ applied to $x=\frac{a}{b}$ acts in the exactly same way. It follows that the computation of $\gcd(F_{n+1},F_n)$ requires $n$ steps since it travels the convergents $[1],[1;1],[1;1,1],\ldots$ of $\frac{F_{n+1}}{F_n}$ in the opposite direction. Additionally, $\frac{F_{n+1}}{F_n}$ is the rational number $>1$ with a continued fraction having length $n$ and the least numerator/denominator: the terms of a continued fraction, with the only exception of the very first one, cannot be smaller than $1$. It follows that when considering all the continued fractions with the same length, the minimum of $\frac{a}{b}\to |a|+|b|$ is attained by $[0;1,1,1,\ldots]$.
Best Answer
anon's answer: $$ \gcd(F_{n+1},F_{n+2}) = \gcd(F_{n+1},F_{n+2}-F_{n+1}) = \gcd(F_{n+1},F_n). $$ Therefore $$ \gcd(F_{n+1},F_n) = \gcd(F_2,F_1) = \gcd(1,1) = 1. $$ In other words, any two adjacent Fibonacci numbers are relatively prime.
Since $$\gcd(F_n,F_{n+2}) = \gcd(F_n,F_{n+1}+F_n) = \gcd(F_n,F_{n+1}), $$ this is also true for any two Fibonacci numbers of distance $2$. Since $(F_3,F_6) = (2,8)=2$, the pattern ends here - or so you might think...
It is not difficult to prove that $$F_{n+k+1} = F_{k+1}F_{n+1} + F_kF_n. $$ Therefore $$ \gcd(F_{n+k+1},F_{n+1}) = \gcd(F_kF_n,F_{n+1}) = \gcd(F_k,F_{n+1}). $$ Considering what happened, we deduce $$ (F_a,F_b) = F_{(a,b)}. $$