Prove that $\gcd(F_{3K},L_{3k}) \equiv 2$

Question

Following this definition $L_K = F_{K-1} + F_{K+1}$

We have that $\gcd(F_{3K},L_{3k}) = \gcd(F_{3k}, F_{3k+1} + F_{3k-1}) =\gcd(F_{3k}, 2F_{3k-1})$

I don't know where to go from here.

How do I prove that $\gcd(F_{3k}, 2F_{3k-1})\equiv 2$

Answer 1

First, let us prove by induction that $F_{3k}$ is even.

We have $F_1=F_2=1,F_3=2$. Suppose that $F_{3k-2}\equiv F_{3k-1}\equiv 1,F_{3k}\equiv 0\pmod 2$. Then, $$F_{3k+1}\equiv 1+0\equiv 1,\quad F_{3k+2}\equiv 0+1\equiv 1,\quad F_{3k+3}\equiv 1+1\equiv 0\pmod 2$$

Therefore, we have that $F_{3k}$ is even.

Second, we have that $\gcd(F_n,F_{n+1})=1$. See, for example, Fibonacci Numbers $F_n$ and $F_{n + 1}$ are relatively prime for all $n \geq 0$..

It follows from these that $\gcd(F_{3k},2F_{3k-1})=2$.