# Proving That Consecutive Fibonacci Numbers are Relatively Prime

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