# Thread: Prove that the gcd of two consecutive Fibonacci numbers is 1.

1. ## Prove that the gcd of two consecutive Fibonacci numbers is 1.

Prove that the gcd of two consecutive Finonacci numbers is 1.

Also identify the ratio $\displaystyle F_{n+1}/F_n$ of consecutive Fibonacci numbers and try to identify the limit.

2. Originally Posted by mathwizard
Prove that the gcd of two consecutive Finonacci numbers is 1.
By definition, $\displaystyle F_{n+1} = F_n + F_{n-1}$.

Assume the $\displaystyle (F_{n+1},F_n) = d$. This implies $\displaystyle d|F_{n+1}, d|F_n$ and thus $\displaystyle d|F_{n-1}$. We can thus recursively(or reverse inductively) claim that $\displaystyle d|F_n \Rightarrow d|F_{n-1}$. Proceeding until n=2, we find that our hypothesis implies $\displaystyle d|F_2,d|F_1 = 1 \Rightarrow d|1 \Rightarrow d=1$

Thus $\displaystyle (F_{n+1},F_n) = 1$ for all positive integers n.

Originally Posted by mathwizard
Also identity the ratio $\displaystyle F_{n+1}/F_n$ of consecutive Fibonacci numbers and try to identity the limit.
By definition, $\displaystyle F_{n+1} = F_n + F_{n-1}$

If you prove that the limit exists, finding it can be easy.

So by definition, $\displaystyle \frac{F_{n+1}}{F_n} = 1 + \frac{F_{n-1}}{F_n}$.

Let the limit of the ratio be L, then $\displaystyle \lim_{n \to \infty} \frac{F_{n+1}}{F_n} = \lim_{n \to \infty} \frac{F_{n}}{F_{n-1}} = L$

So $\displaystyle \frac{F_{n+1}}{F_n} = 1 + \frac{F_{n-1}}{F_n} \Rightarrow L = 1 + \frac1{L}$.

So solve the quadratic and choose the appropriate root.

3. Originally Posted by mathwizard
Prove that the gcd of two consecutive Finonacci numbers is 1.
We can prove something really shocking. Let $\displaystyle F_n$ denote the $\displaystyle n$-th Fibonnaci number. We will prove $\displaystyle \gcd (F_n, F_m) = F_{\gcd(n,m)}$. WLOG say $\displaystyle m\geq n$. Let us apply the Euclidean algorithm to get,
$\displaystyle \left\{ \begin{array}{c} m = q_1n + r_1 \\ n = q_2 r_1+r_2 \\ r_1 = q_3 r_2 + r_3 \\ ... \\ r_{k-2} = q_k r_{k-1} + r_k \\ r_{k-1} = q_{k+2}r_k + 0 \end{array} \right.$
The Euclidean algorithm tells us that if $\displaystyle a = qb + r$ then $\displaystyle \gcd(a,b) = \gcd(b,r)$. It turns out (we will prove this soon) that we have a similar situation with Fibonacci numbers, i.e. $\displaystyle \gcd(F_a,F_b) = F(F_b,F_r)$. If we assume this fact for now than: $\displaystyle \gcd(F_n,F_m) = \gcd( F_{r_1}, F_n) = ... = \gcd(F_{r_{k-1}},F_{r_k})$. Thus, the problem reduces to computing $\displaystyle \gcd (F_{r_{k-1}},F_{r_k})$. This ends up being (we will show this soon) equal to $\displaystyle F_{r_k}$ which is in fact $\displaystyle F_{\gcd(n,m)}$ by the Euclidean algorithm.

To establish the above facts that we used we need an identity. This identity is $\displaystyle F_{m+n} = F_{m-1}F_n+F_mF_{n+1}$ for $\displaystyle m\geq 2$. This is established by using basic induction. With this identity we can prove that if $\displaystyle n,m\geq 1$ then $\displaystyle F_n|F_{nm}$. This is proven by induction as well: the inductive step is to note $\displaystyle F_{n(k+1)} = F_{nk+n}= F_{nk-1}F_n+F_{nk}F_{n+1}$ and now use induction.

We are now in the position to prove if $\displaystyle a=qb+r$ then $\displaystyle \gcd(F_a,F_b) = \gcd(F_b,F_r)$ (note the fact that $\displaystyle \gcd(F_{r_{k-1}},F_{r_k}) = F_{r_k}$ will follow since $\displaystyle r_k | r_{k-1}$). By identity we have $\displaystyle \gcd(F_a,F_b) =\gcd(F_{qb+r},F_b) = \gcd(F_{qb-1}F_r+F_{qb}F_{r+1},F_b)$. But since $\displaystyle b|qb$ we know (from above paragraph) that $\displaystyle F_b | F_{qb}$. Therefore, $\displaystyle \gcd(F_{qb-1}F_r+F_{qb}F_{r+1},F_b) = \gcd(F_{qb-1}F_r,F_b)$. If we can show that $\displaystyle \gcd(F_{qb-1},F_b)=1$ then it will mean that $\displaystyle \gcd(F_{qb-1}F_r,F_b) = \gcd(F_r,F_b)$. Thus, problem is reduced to proving $\displaystyle \gcd(F_{qb-1},F_b)=1$. Let $\displaystyle d=\gcd(F_{qb-1},F_b)$. Since $\displaystyle d|F_b$ and $\displaystyle F_b|F_{qb}$ (from above) it means $\displaystyle d|F_{qb}$. But then it means $\displaystyle d|F_{qb-1}$ and $\displaystyle d|F_{qb}$. It means $\displaystyle d=1$ since $\displaystyle \gcd(F_{qb-1},F_{qb})=1$ as Isomorphism showed.

4. Originally Posted by ThePerfectHacker
We can prove something really shocking. Let $\displaystyle F_n$ denote the $\displaystyle n$-th Fibonnaci number. We will prove $\displaystyle \gcd (F_n, F_m) = F_{\gcd(n,m)}$.
Good show, TPH! That is really a beautiful result.

5. this is not related to mathwizard's question, but, i hope, some memebrs find it interesting. anyway ... my apologies for posting

something off-topic!

i think the most fascinating fact about Fibonacci sequence is that it's periodic modulo any $\displaystyle n \geq 2.$ for example Fibonacci sequence

modulo 3 becomes: $\displaystyle 1,1,2,0,2,2,1,0,1,1,2,0,2,2,1,0, ... \ .$ here $\displaystyle 1,1,2,0,2,2,1,0$ repeats in the sequence. so the period is 8.

as far as i know finding a general formula for the period of Fibonacci sequence modulo a given number n is an open problem!!

6. Originally Posted by mathwizard
Also identify the ratio $\displaystyle F_{n+1}/F_n$ of consecutive Fibonacci numbers and try to identify the limit.
Consider the equation $\displaystyle x^2=x+1$. There are two solutions, $\displaystyle \phi = \tfrac{1}{2}(1+\sqrt{5})$ and $\displaystyle \theta = \tfrac{1}{2}(1-\sqrt{5})$. This means, $\displaystyle \phi^2 = \phi + 1$. Multiply by $\displaystyle \phi$ to get $\displaystyle \phi^3 = \phi^2 + \phi = (\phi+1)+\phi=2\phi+1$. Multiply again to get, $\displaystyle \phi^4 = 2\phi^2 + \phi = 2(\phi+1)+\phi = 3\pi+2$. Do it again, $\displaystyle \phi^5 = 5\pi +3$. The pattern should be clear, $\displaystyle \phi^n = F_n \phi+F_{n-1}$. This can of course be fully justified with induction. Likewise, doing it with $\displaystyle \theta$ we get $\displaystyle \theta^n = F_n \theta + F_{n-1}$. Subtracting the two equations we get $\displaystyle \phi^n - \theta^n = F_n ( \phi - \theta)$. Thus, $\displaystyle F_n = \tfrac{1}{\sqrt{5}}\left[ (\tfrac{1+\sqrt{5}}{2})^n - (\tfrac{1-\sqrt{5}}{2})^n \right]$. Therefore, $\displaystyle \tfrac{F_{n+1}}{F_n} = \tfrac{(1+\sqrt{5})^{n+1} - (1-\sqrt{5})^{n+1}}{2(1+\sqrt{5})^n - 2(1-\sqrt{5})^n}$. This gives us a formula for computing the Fibonacci ratio.

This is Mine 1th Post!!! And my 1th Celebration!!!