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

**mathwizard** · June 20th 2008, 10:55 PM

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.

**Isomorphism** · June 20th 2008, 11:16 PM

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.

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.

**ThePerfectHacker** · June 21st 2008, 07:01 PM

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.

**Reckoner** · June 21st 2008, 07:34 PM

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.

**NonCommAlg** · June 21st 2008, 10:10 PM

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!!

**ThePerfectHacker** · June 22nd 2008, 07:04 AM

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!!!

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

LinkBack

Thread Tools

Display

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

Similar Math Help Forum Discussions

[SOLVED] Prove: each square is the sum of 2 consecutive triangular numbers

Find three consecutive numbers that add up to these numbers

The sum of certain consecutive odd numbers is 57^2 – 13^2. Find the numbers.

Proving Lucas Numbers and Fibonacci Numbers

Consecutive numbers

Search Tags