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