5.4 gcd of generalized Fibonacci and Lucas numbers 205
5.4 gcd of generalized Fibonacci and Lucas numbers
Givenaandb, the generalized Fibonacci sequenceF(a, b)
Fn+1=aFn+bFn− 1 ,F 0 =0,F 1 =1.There is also an accompanying Lucas sequenceL(a, b)
Ln+1=aLn+bFn− 1 ,L 0 =2,L 1 =a.Theorem 5.4.Letaandbbe relatively prime integers. The associated
Fibonacci and Lucas sequences satisfy
gcd(um,un)=ugcd(m,n).Examples
(a, b) Fn(a,b) L(na,b) Lucas
(1,1) Fn Fibonacci Ln Lucas
(1,−1) periodic periodic
(2,−1) n natural 2 constant
(3,−2) 2 n−1 Mersenne 2 n+1 Fermat(11,−10) (^1) n repunits (^10) k− 11
Corollary 5.5. 1.gcd(2m− 1 , 2 n−1) = 2gcd(m,n)− 1.
2.gcd(Fm,Fn)=Fgcd(m,n).
3.gcd(1m, (^1) n)=1gcd(m,n).