# Prove that any two consecutive terms of the Fibonacci sequence are relatively prime

Prove that any two consecutive terms of the Fibonacci sequence are relatively prime.

My attempt:

We have $f_1 = 1, f_2 = 1, f_3 = 2, \dots$, so obviously $\gcd(f_1, f_2) = 1$.
Suppose that $\gcd(f_n, f_{n+1}) = 1$; we will show that $\gcd(f_{n+1}, f_{n+2}) = 1$. Consider $\gcd(f_{n+1}, f_{n+2}) = \gcd(f_{n+1}, f_{n+1} + f_n)$ because $f_{n+2} = f_{n+1} + f_n.$
Then $\gcd(f_{n+1}, f_{n+1} + f_n) = \gcd(f_{n+1}, f_{n}) = 1$ (gcd property).

Hence, $\gcd(f_n, f_{n+1}) = 1$ for all $n > 0$.

Am I on the right track?
Any feedback would be greatly appreciated.

Thanks,

• Your argument is correct! However, you have a minor typo - you wrote $f_3=1$, instead of $f_3=2$. Mar 1, 2011 at 7:25
• That's correct (except for $f_3=1$, but that's immaterial to the proof anyway). Mar 1, 2011 at 7:25
• You are right...
– user17762
Mar 1, 2011 at 7:26
• @all: Thank you. I corrected the typo.
– Chan
Mar 1, 2011 at 7:42
• More generally, $\mbox{gcd}(f_m,f_n)=f_{\mbox{gcd}(m,n)}$. See en.wikipedia.org/wiki/…
– lhf
Mar 1, 2011 at 14:56

Congratulations, you have solved it. You have used the fact that $$\gcd(a+b,b)=\gcd(a,b)$$

Your proof is good. For reference, I have a proof without induction that uses Cassini's identity, $$f_{n-1}f_{n+1} - f_nf_n = (-1)^n,$$ which is proved directly at that Wikipedia page and in another direct way at Show $F_{n+1} \cdot F_{n-1} = F_n^2 + (-1)^n$ for all $n \in \mathbb{N}$.

According to whether $n$ is even or odd, we have $$f_{n-1}f_{n+1} - f_nf_n = 1 \qquad \text{or} \qquad f_nf_n - f_{n-1}f_{n+1} = 1.$$

Now, the gcd of $f_n$ and $f_{n+1}$ may be defined alternatively and equivalently as the least positive integer that can be written in the form $pf_n + qf_{n+1}$ where $p$ and $q$ are integers. Because the coefficients of $f_n$ and $f_{n+1}$ in that pair of equations are Fibonacci numbers, hence integers, and because there is no positive integer less than $1$, gcd$(f_n, f_{n+1}) = 1$. Thus, any two consecutive terms of the Fibonacci sequence are relatively prime.

Another approach. suppose $gcd(f_{n+1}, f_{n}) = d$. Then since $f_{n+1} = f_n + f_{n-1}$, $gcd(f_n, f_{n-1}) \ne 1$ and by infinite descent we will end up with n = 4 and n = 3 where gcd(2,3) = 1. Contradiction.

• I hope you meant $\gcd(3,2) = 1$. But, by infinite descent if you end up with $n+1=4$ and $n=3$, then how it came to $n+1=3$, and $n=2$. Feb 17, 2021 at 2:33
• $f_4 = 3, f_3 = 2$
– sku
Feb 17, 2021 at 7:09

Your proof is good. For reference, I have a similar proof by induction:

The claim is true for the first few pairs of consecutive Fibonacci numbers, so assume it is true up to $f_{n+1}$ so that gcd$(f_{n}, f_{n+1}) = 1$. Then by Bézout's identity, there exist integers $x$ and $y$ such that $xf_{n} + yf_{n+1} = 1$. So \begin{align} 1 & = xf_{n} + yf_{n+1}\\ & = x(f_{n+2} - f_{n+1}) + yf_{n+1}\\ & = (y - x) f_{n+1} + xf_{n+2}. \end{align} Now, the gcd of $f_{n+1}$ and $f_{n+2}$ may be defined alternatively and equivalently as the least positive integer that can be written in the form $uf_{n+1} + vf_{n+2}$ where $u$ and $v$ are integers. Because $y - x$ and $x$ are integers and there is no positive integer than $1$, gcd$(f_{n+1}, f_{n+2}) = 1$. Hence, the claim holds for $n + 2$ whenever it holds for $n + 1$, and so the induction principle guarantees that it holds for every pair of consecutive Fibonacci numbers.

Remark: I called this proof similar to yours because Bézout's identity is used to prove the gcd property that you used.

Using induction/modular arithmetic:

For n = 1, we see that $$F_n$$ and $$F_{n+1}$$ are relatively prime.

For the inductive step, we assume $$F_n$$ and $$F_{n+1}$$ are relatively prime, and show this implies $$F_{n+1}$$ and $$F_{n+2}$$ are relatively prime.

By the inductive assumption, for any prime $$p$$ for which $$p|F_{n+1}$$, $$p∤F_n$$. With modular arithmetic, this statement becomes $$F_{k+1} ≡ 0⠀mod(p)$$ and $$F_k ≢ 0⠀mod(p)$$Using the definition of the Fibonacci sequence, we can change the first congruence to $$F_{k+2} - F_k ≡ 0⠀mod(p)$$ $$F_{k+2} ≡ F_k≢ 0⠀mod(p)$$ Modular congruence is transitive (this is pretty clear, i.e. since $$3≡7≡15⠀mod(4),⠀ 3≡15⠀mod (4)$$.) Thus $$F_{k+2} ≢0⠀mod(p)$$, meaning $$p∤F_{k+2}$$ and $$F_{n+1}$$ and $$F_{n+2}$$ are relatively prime.