204 Greatest common divisor
5.3 Cassini formula for Fibonacci numbers
The Fibonacci numbersFnare defined recursively by
Fn+1=Fn+Fn− 1 ,F 0 =0,F 1 =1.The first few Fibonacci numbers are
n 0123456 7 8 9 1011 12...
Fn 01123581321345589144 ...It is easy to see that
gcd(Fn+1,Fn)=gcd(Fn,Fn− 1 )
=gcd(Fn− 1 ,Fn− 2 )
..
.
=gcd(F 2 ,F 1 )=1.However, following the euclidean algorithm, we obtain the Cassini for-
mula
Fn+1Fn− 1 −Fn^2 =(−1)n.
k rk qk xk yk
− 1 Fn+1 ∗∗∗ 1 0
0 Fn 1 0 1
1 Fn− 1 1 F 1 −F 2
2 Fn− 2 1 −F 2 F 3
3 Fn− 3 1 F 3 −F 4
..
.
n− 3 F 3 1 (−1)n−^2 Fn− 3 (−1)n−^1 Fn− 2
n− 2 F 2 1 (−1)n−^1 Fn− 2 (−1)nFn− 1
n− 1 F 1 1 (−1)nFn− 1 (−1)n+1Fn
n 0 ∗∗∗