Divisibility of Odd Fibonaccis
The smallest positive index m such that the Fibonacci number Fm 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: Fn+k = (1/2)(FnLk + FkLn), where Ln are Lucas numbers. From here F3n = (1/2)Fn(L2n + Ln2). Like Fibonacci numbers, exactly every third Lucas number is even. Hence, the parity of L2n is the same as the parity of Ln. Hence, L2n + Ln2 is divisible by 2. Let us denote Gn = (1/2)(L2n + Ln2).
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 F3n and doesn’t divide Fn. Hence, p divides Gn. On the other hand, we can show that Gn = 5Fn2 + 3(-1)n. Hence, the only common divisor that Fn and Gn can have is 3. Let us take any prime divisor s of Gn other than 3. We see that F3n is divisible by s while Fn is not. The rank of apparition of 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 Gn is the set of primes that do not divide odd Fibonaccis.
Here’s a bit more info about the sequence Gn. It is sequence A047946 in the Online Encyclopedia of Integer Sequences. It is a recurrence: Gn=2*Gn-1+2*Gn-2-Gn-3. 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.
Share:
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 amMisha:
Yet another number-theoretic puzzle. Enjoy.
19 May 2008, 8:55 am