Being $f_n$ a Fibonacci-like sequence, prove that if $f_n$ and $f_{n-1}$ are coprimes, then $f_n$ and $f_{n+1}$ are coprimes. $f_{n}=f_{n-1}+f_{n-2}$
I think I proved this by combining mathematical induction and modus tollens, but not sure about the correctness of the proof. Maybe we can get a fix or a totally different proof.
Suppose that $f_n$ and $f_{n+1}$ aren't coprimes, so, exists $1\neq a\in\mathbb N$ such that $f_n=a·v$ and $f_{n+1}=a·w$. Then $a·w=f_{n+1}=f_n+f_{n-1}=a·v+f_{n-1}$ or $f_{n-1}=a(w-v)$. So is, $f_n$ and $f_{n-1}$ cannot be coprimes either. Now, we negate the conclusion: $f_n$ and $f_{n-1}$ are coprimes and the premise is negated: $f_n$ and $f_{n+1}$ are coprimes.
Thanks in advance.
 A: The proof looks essentially correct, though I might not lay it out that way.  For example, I do not find $1\neq a\in\mathbb N$ attractive. There are also a lot of negative statements. So saying the same thing a slightly different way:


*

*If $f_{n+1}=aw$ and $f_{n}=av$ for integers $a,v,w$, then $f_{n-1}=f_{n+1}-f_{n}=a(w-v)$  

*so any common factor of $f_{n}$ and $f_{n+1}$ is also a factor of $f_{n-1}$

*but the highest common factor of $f_{n-1}$ and $f_{n}$ is $1$ since they are coprime

*so the highest common factor of $f_{n}$ and $f_{n+1}$ is also $1$, and thus they too are coprime
A: Using Euclid's lemma:
$$
\gcd(f_{n+1},f_n)=\gcd(f_n,f_{n+1}-f_n)=\gcd(f_n,f_{n-1})
$$
A: Slighly different but still elementary: 
Suppose that $f_n$ and $f_{n-1}$ are co-primes. Let $p$ be any prime factor of $f_n$. It means that:
$$f_n\equiv0, \space f_{n-1}\not\equiv0\quad\text{(mod p)} \implies f_{n+1}=f_n+f_{n-1}\not\equiv 0\quad \text{(mod p)}$$
So $f_{n+1}$ is not divisible by any factor of $f_n$ and therefore these numbers must be co-prime.
