The Problem:

Prove that consecutive Fibonacci numbers are relatively prime.

I have seen proofs where people use induction and show that if $\gcd(F_n, F_{n+1})=1$, then $\gcd(F_{n+1}, F_{n+2})=1$ through the Fibonacci property.

My proof uses induction as well, but in a different way.

We will use induction to show that if such a base case exists that $F_{n}$ and $F_{n+1}$ are both divisible by some integral $k \ge 2$, then all $F_{i}$ are divisible by $k$.

$$F_{n} \equiv F_{n+1} \equiv 0 \pmod{k}$$ $$F_{n} \equiv F_{n}+F_{n-1} \equiv 0 \pmod{k}$$ $$F_{n} \equiv F_{n-1} \equiv 0 \pmod{k}$$

Since $F_{3}=2$ and $F_4=3$ are not divisible be any common integer $k \ge 2$, our assumption is wrong. Hence, $F_{n}$ and $F_{n+1}$ are relatively prime.


It is a waste of time to use modular arithmetic for this. What you proved was that$$k\mid F_n\wedge k\mid F_{n+1}\implies k\mid F_{n-1},$$which is indeed correct. But, after having done this, I think that your best option is to say that you are using the well-ordering principle: if there was some $n\in\mathbb N$ such that $F_n$ and $F_{n+1}$ are not coprime, you take the smallest such $n$. Of course, $n$ cannot be $1$, since $F_1$ and $F_2$ are coprime. So, $n-1\in\mathbb N$ and it follows from what you proved that $F_{n-1}$ and $F_n$ are coprime too. This contradicts the definition of $n$.


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.