45
$\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$
5
  • 4
    $\begingroup$ Your argument is correct! However, you have a minor typo - you wrote $f_3=1$, instead of $f_3=2$. $\endgroup$ Mar 1, 2011 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, 2011 at 7:25
  • 1
    $\begingroup$ You are right... $\endgroup$
    – user17762
    Mar 1, 2011 at 7:26
  • $\begingroup$ @all: Thank you. I corrected the typo. $\endgroup$
    – Chan
    Mar 1, 2011 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, 2011 at 14:56

5 Answers 5

22
$\begingroup$

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

$\endgroup$
0
6
$\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$
2
$\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$
2
  • $\begingroup$ 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$. $\endgroup$
    – jiten
    Feb 17, 2021 at 2:33
  • 1
    $\begingroup$ $f_4 = 3, f_3 = 2$ $\endgroup$
    – sku
    Feb 17, 2021 at 7:09
1
$\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$
0
$\begingroup$

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.

$\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.