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

• Jun 20th 2008, 10:55 PM
mathwizard
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.
• Jun 20th 2008, 11:16 PM
Isomorphism
Quote:

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.

Quote:

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.
• Jun 21st 2008, 07:01 PM
ThePerfectHacker
Quote:

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.
• Jun 21st 2008, 07:34 PM
Reckoner
Quote:

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.
• Jun 21st 2008, 10:10 PM
NonCommAlg
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!!
• Jun 22nd 2008, 07:04 AM
ThePerfectHacker
Quote:

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 1:):):):)th Post!!! And my 1:):)th Celebration!!!