9 Divides no Odd Fibonacci
I stumbled upon the following sentence in the MathWorld article on the Fibonacci numbers: “No odd Fibonacci number is divisible by 17.” I started wondering if there are other numbers like that. Of course there are — no odd Fibonacci number is divisible by 2. But then, an odd number need not be a Fibonacci number in order not to be divisible by 2.
So, let’s forget about 2 and think about odd numbers. How do we know that the infinite Fibonacci sequence never produces an odd number that is divisible by 17? Is 17 the only such odd number? Is 17 the smallest such odd number? If there are many such odd numbers, how do we calculate the corresponding sequence?
We’ll start with a general question: How can we approach puzzles about the divisibility of Fibonacci numbers? Suppose K is an integer. Consider the sequence aK(n) = Fn(mod K), of Fibonacci numbers modulo K. The cool thing about this sequence is that it is periodic. If it is not immediately obvious to you, think of what happens when a pair of consecutive numbers in the sequence aK(n) gets repeated. As a bonus for thinking you will get an upper bound estimate for this period.
Let us denote the period of aK(n) by PK. By the way, this period is called a Pisano period. From the periodicity and the fact that aK(0) = 0, we see right away that there are infinitely many Fibonacci numbers divisible by K. Are there odd numbers among them? If we trust MathWorld, then all of the infinitely many Fibonacci numbers divisible by 17 will be even.
How do we examine the divisibility by K for odd Fibonacci numbers? Let us look at the Fibonacci sequence modulo 2. As we just proved, this sequence is periodic. Indeed, every third Fibonacci number is even. And the evenness of a Fibonacci number is equivalent to this number having an index divisible by 3.
Now that we know the indices of even Fibonacci numbers we can come back to the sequence aK(n). In order to prove that no odd Fibonacci number is divisible by K, it is enough to check that all the zeroes in the sequence aK(n) have indices divisible by 3. We already have one zero in this sequence at index 0, which is by divisible by 3. Because the sequence aK(n) is periodic, it will start repeating itself at aK(PK) . Hence, we need to check that PK is divisible by 3 and all the zeroes up to aK(PK) have indices divisible by 3. When K = 17 it is not hard to do the calculations manually. If you’d like, try this exercise. To encourage (or perhaps to discourage) you, here’s an estimate of the scope of the work for this exercise: the Pisano period for K = 17 is 36.
After I checked that no odd Fibonacci number is ever divisible by 17, I wanted to find the standard solution for this statement and followed the trail in MathWorld. MathWorld sent me on a library trip where I found the proof of the statement in the book Mathematical Gems III by Ross Honsberger. There was a proof there alright, but it was tailored to 17 and didn’t help me with my questions about other such odd numbers.
The method we developed for 17 can be used to check any other number. I trusted this task to my computer. To speed up my program, I used the fact that the Pisano period for K is never more than 6K. Here is the sequence calculated by my trustworthy computer, which I programmed with, I hope, equal trustworthiness:
- A133246 Odd numbers n with the property that no odd Fibonacci number is divisible by n.
9, 17, 19, 23, 27, 31, 45, 51, 53, …
The sequence shows that 9 is the smallest odd number that no odd Fibonacci is ever divisible by, and 17 is the smallest odd prime with this same property. Here is a trick question for you: Why is this property of 17 more famous than the same property of 9?
Let us look at the sequence again. Is this sequence infinite? Obviously, it should include all multiples of 9 − hence, it is infinite. What about prime numbers in this sequence? Is there an infinite number of primes such that no odd Fibonacci number is divisible by them? While I do not know the answer, it’s worth investigating this question a little bit further.
From now on, let K be an odd prime. Let us look at the zeroes of the sequence aK(n) more closely. Suppose a zero first appears at the m-th place of aK(n). Then aK(m+1) = aK(m+2) = a. In this case the sequence starting from the m-th place is proportional modulo K to the sequence aK(n) starting from the 0-th index. Namely, aK(n+m) = a*aK(n) (mod K). As a is mutually prime with K, then aK(n+m) = 0 iff aK(n) = 0. From here, for any index g that is a multiple of m, aK(g) = 0. Furthermore, there are no other zeroes in the sequence aK(n). Hence, the appearances of 0 in the sequence aK(n) are periodic with period m.
By the way, m is called a fundamental period; and we just proved that the Pisano period is a multiple of the fundamental period for prime K. Hence, the fact that no odd Fibonacci number is divisible by K is equivalent to the fact that the fundamental period is not divisible by 3. It is like saying that if the smallest positive Fibonacci number divisible by an odd prime K is even, then no odd Fibonacci number is divisible by K.
If the remainder of the fundamental period modulo 3 were random, we would expect that about every third prime number would not divide any odd Fibonacci numbers. In reality there are 561 such primes among the first 1,500 primes (including 2). This is somewhat more than one third. This gives me hope that there is a non-random reason for such primes to exist. Consequently, it may be possible to prove that the sequence of prime numbers that do not divide odd Fibonacci numbers is infinite.
Can you prove that?Share:
Tanya Khovanova’s Math Blog » Blog Archive » Blog Spam:
[…] comment was placed on my Fibonacci entry, where I think I gave more than enough proofs. So I read all the small print that accompanied the […]25 April 2008, 12:53 pm
Tanya Khovanova’s Math Blog » Blog Archive » Divisibility of Odd Fibonaccis:
[…] Even Fibonaccis have indices divisible by 3. That means that if for some p the rank of apparition of p is divisible by three, all the Fibonaccis that are divisible by p are even. Therefore, no odd Fibonacci divides p. I already discussed this subject in my previous post “9 Divided no Odd Fibonacci.” […]7 May 2008, 6:54 am
Tanya Khovanova’s Math Blog » Blog Archive » Odd Fibonacci and Odd Lucas Numbers:
[…] 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 […]3 February 2009, 7:32 pm