Fibonacci numbers

This post is about an interesting property of the Fibonacci numbers. The Fibonacci numbers, as you know, are entries of the sequence

1,1,2,3,5,8,13,21,34,55,89,144,...,
where any given entry is the sum of the previous two terms. The fifth Fibonacci number is 5, which is 3+2, the sum of the fourth and the third entries. The sixth one is 8, which you get by adding the fifth term to the fourth, etc. If we denote the r^th term by , then

You must have seen any number of popular math articles dealing with the Fibonacci numbers and the golden ratio. The golden ratio is the number which is approximately equal to 1.618. If you consider the successive ratios of the Fibonacci numbers you'll see that these ratios approach the golden ratio as you do the computation with larger and larger entries. A math student might prefer to say that tends to as n tends to infinity.

Love a bit of hype? Then you may want to check out this Guardian article, or even better, give a Google search, and check out a few random links. And don't be upset if you find out that you aren't perfect (check out the comment here by Linda)! On a serious note, you could find a lot of intricate patterns among the Fibonacci numbers here.

To warm up to what we are getting at, let's start with the observation that if n divides m, then divides . This isn't hard to be proved. In particular, you see that if n is not a prime number, cannot be a prime either. Mind you, you cannot conclude that is a prime if n is a prime. That's not correct. For instance, 19 is a prime, but

At this point, you may want to have a look at the factorisations of the first few Fibonacci numbers here. As an aside, perhaps I need to add that it's not known "how many" Fibonacci numbers are prime numbers. There could be infinitely many Fibonacci primes, but this is neither proved nor disproved. In general, questions connecting the two basic operations of addition and multiplication are exceedingly difficult. As Heisuke Hironaka, a well-known Japanese mathematician, put it recently,

[i]f you really think about the relation between addition and multiplication, it's amazingly strange. For instance, 5 is a prime number, but if you add 1, it immediately becomes 6, which is 2 times 3 - two different numbers come out. It seems stupid to make a big fuss about it, but if you really think about why multiplication comes up in this strange way, it is very closely related to many [difficult] questions in number theory.

In any case, let's focus on the Fibonacci numbers at the prime positions. So have a look at the factorisations here. To avoid a few initial exceptions, I'm going to start looking at primes p>5 onwards. Now

etc. See any pattern? The pattern that you are supposed to see is summarised in the following result.

Result: Let p>5 be a prime number. Let q be any prime dividing . Then p divides either q-1 or q+1. Moreover, p divides or .

What follows assumes a bit of undergraduate level math.

Sketch of a proof: Consider the matrix

Observe that

This implies that the order of A in the group divides 4p, where denotes the finite field of q elements. This is because has order 4 modulo q. On the other hand the order of A divides since A is diagonalizable in . Thus the order of A divides the gcd of 4p and . Since p>5, it follows that p divides , which is what we wanted to prove. The second statement easily follows from the first.

P.S: Thanks to froginthewell for an e-mail communication on this topic.

Update (October 18): Professor B. Sury points out that the result can be further strengthened:

Let p>5 be a prime number. Let q be any prime dividing . Then p divides q-1 (respectively q+1) when q divided by 5 has remainder 1 or 4 (respectively 2 or 3).