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

• Jun 20th 2008, 11: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 $F_{n+1}/F_n$ of consecutive Fibonacci numbers and try to identify the limit.
• Jun 21st 2008, 12:16 AM
Isomorphism
Quote:

Originally Posted by mathwizard
Prove that the gcd of two consecutive Finonacci numbers is 1.

By definition, $F_{n+1} = F_n + F_{n-1}$.

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

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

Quote:

Originally Posted by mathwizard
Also identity the ratio $F_{n+1}/F_n$ of consecutive Fibonacci numbers and try to identity the limit.

By definition, $F_{n+1} = F_n + F_{n-1}$

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

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

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

So $\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, 08: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 $F_n$ denote the $n$-th Fibonnaci number. We will prove $\gcd (F_n, F_m) = F_{\gcd(n,m)}$. WLOG say $m\geq n$. Let us apply the Euclidean algorithm to get,
$\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 $a = qb + r$ then $\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. $\gcd(F_a,F_b) = F(F_b,F_r)$. If we assume this fact for now than: $\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 $\gcd (F_{r_{k-1}},F_{r_k})$. This ends up being (we will show this soon) equal to $F_{r_k}$ which is in fact $F_{\gcd(n,m)}$ by the Euclidean algorithm.

To establish the above facts that we used we need an identity. This identity is $F_{m+n} = F_{m-1}F_n+F_mF_{n+1}$ for $m\geq 2$. This is established by using basic induction. With this identity we can prove that if $n,m\geq 1$ then $F_n|F_{nm}$. This is proven by induction as well: the inductive step is to note $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 $a=qb+r$ then $\gcd(F_a,F_b) = \gcd(F_b,F_r)$ (note the fact that $\gcd(F_{r_{k-1}},F_{r_k}) = F_{r_k}$ will follow since $r_k | r_{k-1}$). By identity we have $\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 $b|qb$ we know (from above paragraph) that $F_b | F_{qb}$. Therefore, $\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 $\gcd(F_{qb-1},F_b)=1$ then it will mean that $\gcd(F_{qb-1}F_r,F_b) = \gcd(F_r,F_b)$. Thus, problem is reduced to proving $\gcd(F_{qb-1},F_b)=1$. Let $d=\gcd(F_{qb-1},F_b)$. Since $d|F_b$ and $F_b|F_{qb}$ (from above) it means $d|F_{qb}$. But then it means $d|F_{qb-1}$ and $d|F_{qb}$. It means $d=1$ since $\gcd(F_{qb-1},F_{qb})=1$ as Isomorphism showed.
• Jun 21st 2008, 08:34 PM
Reckoner
Quote:

Originally Posted by ThePerfectHacker
We can prove something really shocking. Let $F_n$ denote the $n$-th Fibonnaci number. We will prove $\gcd (F_n, F_m) = F_{\gcd(n,m)}$.

Good show, TPH! That is really a beautiful result.
• Jun 21st 2008, 11: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 $n \geq 2.$ for example Fibonacci sequence

modulo 3 becomes: $1,1,2,0,2,2,1,0,1,1,2,0,2,2,1,0, ... \ .$ here $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, 08:04 AM
ThePerfectHacker
Quote:

Originally Posted by mathwizard
Also identify the ratio $F_{n+1}/F_n$ of consecutive Fibonacci numbers and try to identify the limit.

Consider the equation $x^2=x+1$. There are two solutions, $\phi = \tfrac{1}{2}(1+\sqrt{5})$ and $\theta = \tfrac{1}{2}(1-\sqrt{5})$. This means, $\phi^2 = \phi + 1$. Multiply by $\phi$ to get $\phi^3 = \phi^2 + \phi = (\phi+1)+\phi=2\phi+1$. Multiply again to get, $\phi^4 = 2\phi^2 + \phi = 2(\phi+1)+\phi = 3\pi+2$. Do it again, $\phi^5 = 5\pi +3$. The pattern should be clear, $\phi^n = F_n \phi+F_{n-1}$. This can of course be fully justified with induction. Likewise, doing it with $\theta$ we get $\theta^n = F_n \theta + F_{n-1}$. Subtracting the two equations we get $\phi^n - \theta^n = F_n ( \phi - \theta)$. Thus, $F_n = \tfrac{1}{\sqrt{5}}\left[ (\tfrac{1+\sqrt{5}}{2})^n - (\tfrac{1-\sqrt{5}}{2})^n \right]$. Therefore, $\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!!!