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.

Question

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

Answer 1

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

Answer 2

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.

Answer 3

Using Euclid's lemma: $$ \gcd(f_{n+1},f_n)=\gcd(f_n,f_{n+1}-f_n)=\gcd(f_n,f_{n-1}) $$