Odd Fibonacci and Odd Lucas Numbers

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.


One Comment

  1. Jeff:

    Essay on peer reviewed mathematical journals and retractions.
    There is new website on the internet tracking retractions in general. I think this is great, but there is no real effort put in understanding the process leading up to a retraction. This is the span of time, often years, between the time an article gets published and the time a retraction or list of errata gets published. What happens in this span of time?
    There is an old adage we should all go by, especially the mathematician: trust but verify. As an example, you are not obligated, and by no means ought to, believe Wiles’ proof of Fermat’s Last Theorem until you have verified it for yourself. You can, of course, spend the rest of your life trusting a fellow mathematician of superior mathematical power.
    In the old days, I can see why a given journal would want to maintain an aura of perfection in the sciences. Studies are expensive to reproduce, but not so much so now. But mathematics is not science, it is art, as mathematics is a language. Both are similar though in the sense that they are born of manual processes from the human mind, and thusly prone to error.
    It is well-known and accepted in the world of manufacturing that an expected number of defects will occur, especially in what is called a “stuff-line”. Imagine a row of seated workers placing parts, some requiring proper polarity, into a printed circuit board unit. The unit being assembled moves from left to right, let’s say. The person to the immediate right has the task of verifying that the person to their left inserted the parts in the unit with proper polarity before inserting their own parts. The unit moves down the line for eventual shipment to the customer.
    An analogy here is a mathematician writing a standard proof by induction, which can be tricky and very tedious, as part of an article. The peer review process checks the proof before publication (shipment). There will be defects!
    Every journal has the duty of setting up a formal process for reviewing questions regarding the validity of the results it publishes, especially if the reader gets charged $31.50 for a mathematical article containing fallacious results. This process should be standardized for all journals and for the common good of humanity, and defects must be corrected or noted in the publication. This can all be done electronically nowadays. The days of the journal simply pointing the finger at the author are over. Further, leaving it up to the individual researcher to discover and ignore fallacious results is a disservice to humanity as well.
    Of course some journals are ran like a business nowadays, and even that situation is changing. People want things instantaneously and free of charge and defects. What’s funny and disconcerting, in some ways, is that journals are now eating their own dog food, in some sense, in the form of the creation of the: Impact factor.
    These are called metrics in the world of manufacturing, and of course have their ultimate basis in the language of mathematics. Misapplied metrics can cripple a business. Now imagine that we decide to add retractions, with an appropriate weight, to the computation of a journals impact factor score.

Leave a comment