# Prove that if $n$ is not a multiple of $3$ then $\gcd(F_n,L_n)=1$

I have that $\gcd(F_n,L_n)= \gcd(F_n, 2F_{n-1})$

I also proved earlier that $F_{3n}$ is even but that does that mean that all Fibonacci numbers obey this. In other words if $n$ is not a multiple of $3$ then the corresponding Fibonacci number is odd? How does one prove this?

• Modulo $2$, starting with $F_0=0$, the Fibonaccis go $0,1,1,0,1,1,0,1,1,0,\ldots$. – Lord Shark the Unknown Apr 20 '17 at 18:36

Note that $L_n=F_{n-1}+F_{n+1}$ for all $n$. So $$(F_n,L_n)=(F_n,F_{n-1}+F_{n+1})=(F_n, F_n+2F_{n-1})=(F_n,2F_{n-1})$$ If $n$ is not divisible by $3$, $F_n$ is odd, so that this gcd equals $1$, because also $F_n$ and $F_{n-1}$ are coprime. Otherwise it is $2$.