42
$\begingroup$

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,

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

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

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.