I was interested for some time in the divisibility of odd Fibonacci numbers. Fibonacci numbers are closely related to Lucas numbers. Lucas numbers Ln follow the same recurrence as Fibonacci numbers: Ln = Ln-1 + Ln-2, but with a different start: L0 = 2, L1 = 1. Obviously, every third Fibonacci and every third Lucas number is even.
Primes that divide odd Lucas numbers divide odd Fibonacci numbers. Let us prove this. Suppose a prime p divides an odd Lucas number Lk, then we can use the famous identity F2k = FkLk. We see that p divides F2k. The fact that Lk is odd means that k is not divisible by 3 and so is 2k. Thus F2k is an odd Fibonacci that is divisible by p.
We see that primes that divide odd Lucas numbers are a subset of primes dividing odd Fibonacci numbers. It is easy to see that it is a proper subset. The smallest prime that divides an odd Fibonacci and doesn’t divide any Lucas number is 5.
The next natural question to ask: is there a prime number that divides an odd Fibonacci, doesn’t divide an odd Lucas number, but divides an even Lucas number? Below I show that such a prime doesn’t exist. In other words, that the set of prime factors of odd Lucas numbers is the intersection of the set of prime factors of odd Fibonacci numbers with the set of prime factors of all Lucas numbers.
Let us consider a Fibonacci-like sequence an in a sense that an = an-1 + an-2 for n > 1. Let me denote by bn, the sequence that is an modulo a prime number p. The sequence bn has to be periodic. It could happen that bn is never 0. For example, Lucas numbers are never divisible by 5. Suppose the sequence bn contains a zero. Let us denote r(p) the difference between the indices of two neighboring zeroes in bn. We can prove that r(p) is well-defined, meaning that is doesn’t depend on where you choose your neighboring zeroes. Moreover r(p) doesn’t depend on the sequence you start with (see 9 Divides no Odd Fibonacci for the proof). The number r(p) is called the rank of apparition of the prime p.
As the Fibonacci sequence starts with a zero, then the terms divisible by a prime p are exactly the terms with indices that are multiples of the corresponding rank of apparition. The Lucas sequence doesn’t start with a zero, but we know that L-n = (-1)nLn. That means, if a Lucas number is ever divisible by a prime p, then the smallest positive index for such a number has to be r(p)/2. Also, the indices of the Lucas numbers divisible by p will be odd multiples of r(p)/2.
We know that the indices of even Fibonacci or Lucas numbers are multiples of 3. Hence, a prime number p that divides an odd Fibonacci number must have a rank of apparition that is not divisible by 3, That means that if p ever divides a Lucas number, then it divides a Lucas number with an index of r(p)/2, which is not divisible by 3, meaning that p divides an odd Lucas number. QED.Share: