# Proof about Fibonacci and Lucas numbers (GCD)

• Apr 21st 2010, 06:16 AM
aurah
Proof about Fibonacci and Lucas numbers (GCD)
Hi.
How to prove that GCD(F3k, L3k)=2? and If n dosen't divide with 3 GCD(Fn, Ln)=1
Don't even know how to start that:/....Hope someone can help:)
Ty.
• Apr 21st 2010, 09:26 AM
kompik
Quote:

Originally Posted by aurah
Hi.
How to prove that GCD(F3k, L3k)=2? and If n dosen't divide with 3 GCD(Fn, Ln)=1
Don't even know how to start that:/....Hope someone can help:)
Ty.

Try to show:
a) \$\displaystyle L_n=F_{n+1}+F_{n-1}\$
b) \$\displaystyle \gcd(F_n,F_{n+1})=1\$ for every n.

Using these two properties you can get:
\$\displaystyle \gcd(F_n,L_n)=\gcd(F_n,F_{n+1}+F_{n-1})=\gcd(F_n,F_n+2F_{n-1})=\gcd(F_n,2F_{n-1}\$. This is either 1 or 2, since Fn and F_n-1 are coprime. So you already know that the only possible values are 1 and 2.

To show that they are equal to what you right, just nottice the pattern 0,0,1,0,0,1,.... when looking to the sequence Fn (or Ln) modulo 2.