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,

Solution 1:

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

Solution 2:

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.

Solution 3:

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.

Solution 4:

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.