Tanya Khovanova’s Math Blog

I was interested for some time in the divisibility of odd Fibonacci numbers. Fibonacci numbers are closely related to Lucas numbers. Lucas numbers L_n follow the same recurrence as Fibonacci numbers: L_n = L_n-1 + L_n-2, but with a different start: L₀ = 2, L₁ = 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 L_k, then we can use the famous identity F_2k = F_kL_k. We see that p divides F_2k. The fact that L_k is odd means that k is not divisible by 3 and so is 2k. Thus F_2k 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 a_n in a sense that a_n = a_n-1 + a_n-2 for n > 1. Let me denote by b_n, the sequence that is a_n modulo a prime number p. The sequence b_n has to be periodic. It could happen that b_n is never 0. For example, Lucas numbers are never divisible by 5. Suppose the sequence b_n contains a zero. Let us denote r(p) the difference between the indices of two neighboring zeroes in b_n. 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)ⁿL_n. 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.