## Divisibility of Odd Fibonaccis

The smallest positive index *m* such that the Fibonacci number *F _{m}* is divisible by the number

*p*is called the rank of apparition of

*p*. If

*p*is prime, one can prove that any Fibonacci number that is divisible by

*p*has an index divisible by

*m*.

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.”

Now let’s look more closely at the set of primes that divide no odd Fibonacci. The Fibonacci numbers obey the following identity: *F _{n+k} = (1/2)(F_{n}L_{k} + F_{k}L_{n})*, where

*L*are Lucas numbers. From here

_{n}*F*. Like Fibonacci numbers, exactly every third Lucas number is even. Hence, the parity of

_{3n}= (1/2)F_{n}(L_{2n}+ L_{n}^{2})*L*is the same as the parity of

_{2n}*L*. Hence,

_{n}*L*is divisible by 2. Let us denote

_{2n}+ L_{n}^{2}*G*.

_{n}= (1/2)(L_{2n}+ L_{n}^{2})As we have already discussed before, if no odd Fibonacci is divisible by *p*, *p*‘s rank of apparition is of the form *3n* which means *p* divides *F _{3n}* and doesn’t divide

*F*. Hence,

_{n}*p*divides

*G*. On the other hand, we can show that

_{n}*G*. Hence, the only common divisor that

_{n}= 5F_{n}^{2}+ 3(-1)^{n}*F*and

_{n}*G*can have is 3. Let us take any prime divisor

_{n}*s*of

*G*other than 3. We see that

_{n}*F*is divisible by

_{3n}*s*while

*F*is not. The rank of apparition of

_{n}*s*must be a divisor of

*3n*and not a divisor of

*n*. Hence this rank is divisible by 3. Thus we can see that with the exception of 3, the set of prime divisors of elements of

*G*is the set of primes that do not divide odd Fibonaccis.

_{n}Here’s a bit more info about the sequence *G _{n}*. It is sequence A047946 in the Online Encyclopedia of Integer Sequences. It is a recurrence:

*G*. Thus, we have found a recursive sequence, elements of which have a set of prime divisors which with the exception of 3 is the set of primes that do not divide odd Fibonacci numbers.

_{n}=2*G_{n-1}+2*G_{n-2}-G_{n-3}
## SpeedKills:

I quote from a previous entry:

“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?”

There is a classical result on divisors of Fibonacci numbers ensuring the existence of prime divisors with “rank of apparition” (your notion) equal to any index outside the finite set {1,2,6,12}. Taking such primes for the indices 3^n, n>=1 yields an infinite sequence with the desired property.

The proof of the underlying classical result involves a careful case inspection and is quite lengthy (>10 pages). Since you need the result just for indices 3^n, n>=1 you can get a direct proof by using Walls formula in less than one page.

I hope that helps. With best regards.

11 May 2008, 9:30 am## Misha:

Yet another number-theoretic puzzle. Enjoy.

19 May 2008, 8:55 am