 ONE TO NINE by Andrew Hodges    Page 159: There is an enormous literature on Fibonacci numbers. Some starting points:

Table of the first 300 Fibonacci numbers with factorisation.
The first 1000 Fibonacci numbers
Wolfram MathWorld Fibonacci number pages.

Page 161: These are the hardest problems in the book, but show how quite a difficult question can be answered by arguments of counting and logic which need no more than the kind of thinking that goes into Sudoku.

For the first result, consider the Fibonacci sequence modulo p, starting with the pair (0, 1). Any two consecutive elements (a, b) in the sequence determine the next one (a + b) and the predecessor (b − a), where + and − are both modulo p. The pair (0, 0) can't occur, so there are only p2 − 1 possible pairs. So the sequence must repeat with a cycle of at most this length.

Because the predecessors are also completely determined, the repeating cycle must include (0, 1). Thus (0, 1) must recur within p2 − 1 steps, i.e. there is a Fibonacci number Fs such that p is a factor of Fs and s ≤ p2 − 1.

The second result sharpens this basic result. Define a 0-chain of consecutive pairs to be a sequence that starts with (0, a) and ends with (z, 0) for some a and z, and with no 0 appearing except in those initial and final pairs. For instance, modulo 5, (0, 1), (1, 1), (1, 2), (2, 3), (3, 0) is a 0-chain. The number s, the least number such that Fs = 0 modulo p, is just the length of the 0-chain beginning with (0, 1).

Given a 0-chain, there is a class of (p − 1) 0-chains obtained by multiplying it by (1, 2, 3,... p − 1). These 0-chains are all of the same length s. There are no elements that belong to more than one 0-chain, because given any element you can work backwards to find the unique element of form (0, a) which is the initial element of the 0-chain. The (p − 1) 0-chains account for s(p − 1) distinct pairs. So we have that
s(p − 1) ≤ p2 − 1. Hence s ≤ p + 1.

For the third result we look more generally at chains of length s, starting now with any pair (a, b). The chain will be:

(a, b), (b, a+b), (a+b, a+2b)... (Fr−1a + Frb, Fra + Fr+1b) ... (Fs−2a + Fs−1b, Fs−1a + Fsb)

These pairs have the property that either all of them are proportional, or none of them are. To see this, consider the possibility that (a, b) is proportional to (Fr−1a + Frb, Fra + Fr+1b), for r < s. That is, we ask whether there is some number c such that (ca, cb) = (Fr−1a + Frb, Fra + Fr+1b) modulo p. This is equivalent to:

a (Fra + Fr+1b) = b (Fr−1a + Frb)

which simplifies to Fr (a2 + ab − b2) = 0. Since Fr ≠ 0, the possibility of two pairs being proportional arises only if a2 + ab − b2 = 0. But in this case all the pairs are proportional.

Let f be the number such that fa = b modulo p. Then this condition is equivalent to f2 = f + 1 modulo p, i.e. f must be a golden number modulo p. Does there exist such a number? This is where Gauss's law of quadratic reciprocity gives the answer. Rewrite the equation as (2f − 1)2 = 5 modulo p. Then Gauss tells us that there is a number (2f − 1) whose square is 5, modulo p, if and only if there is a number whose square is p, modulo 5. This happens if p is 1 or 4 modulo 5, i.e. if p ends in 1 or 9 in decimal notation. If p ends in 3 or 7 there is no solution.

Case when p ends in 3 or 7: Every chain consists of non-proportional pairs. So just as with the 0-chains, multiplying a chain by (1, 2, 3, 4... p − 1) must produce (p − 1) chains without any common elements. It follows that all the p2 − 1 pairs can be organised into blocks of size s(p − 1). So s must divide into p + 1.

Case when p ends in 1 or 9. There are two solutions for the golden numbers f, and these account for 2(p − 1) of the p2 − 1 pairs. The remaining (p − 1)2 pairs can be organised into blocks of size s(p − 1). So s must divide into p − 1.

There is a special case when p = 5, so there are 24 pairs to be considered. In this case the equation (2f − 1)2 = 5 modulo p has the single solution 2f = 1, i.e. f = 3. So in this case there are just 4 exceptional pairs (1, 3), (3, 4), (4, 2), (2, 1). The remaining 20 give 4 chains of length 5.

Examples:

For p = 7, s = 8, since 7 is a factor of the 8th Fibonacci number, 21. There are 48 pairs in 6 chains of length 8, determined by the sequences:
0, 1, 1, 2, 3, 5, 1, 6
0, 2, 2, 4, 6, 3, 2, 5
0, 3, 3, 6, 2, 1, 3, 4
0, 4, 4, 1, 5, 6, 4, 3
0, 5, 5, 3, 1, 4, 5, 2
0, 6, 6, 5, 4, 2, 6, 1
and all the chains are 0-chains.

For p=11, s=10, since 11 is a factor of the 10th Fibonacci number, 55. There are 120 pairs to be considered. Since p ends in 1, there are two golden numbers, which are 4 and 8. (16 = 4 + 1, and 64 = 8 + 1, modulo 11). These give 20 exceptional pairs which arise in the sequences:
1, 4, 5, 9, 3
2, 8, 10, 7, 6
1, 8, 9, 6, 4, 10, 3, 2, 5, 7
The remaining 100 pairs are accounted for by the 10 0-chains of length 10.

For p=13, s =7, since 13 is the 7th Fibonacci number. There are no golden numbers. The 168 pairs break down into the 12 0-chains of length 7, and 12 more chains which follow from taking
1, 3, 4, 7, 11, 5, 3
and multiplying it by each of 1, 2, 3,... 11, 12.

For p=23, s=24, since 23 doesn't occur until the very last moment possible, at the 24th Fibonacci number, 46368. There are no golden numbers and the 528 pairs break down into the 22 0-cycles of length 24.

In contrast, p=89 has s=11, since the 11th Fibonacci number 89 is an example of an unexpectedly early-appearing prime. The golden numbers are 10 and 80, giving rise to the 176 exceptional pairs from
1, 10, 11, 21, 32, 53, 85, 49, 45, 5, 50, 55, 16, 71, 87, 69, 67, 47, 25, 72, 8, 80, 88, 79, 78, 68, 57, 36, 4, 40, 44, 84, 39, 34, 73, 18, 2, 20, 22, 42, 64, 17, 81, 9
and 3 times this sequence,
1, 80, 81, 72, 64, 47, 22, 69, 2, 71, 73, 55, 39, 5, 44, 49, 4, 53, 57, 21, 78, 10, 88, 9, 8, 17, 25, 42, 67, 20, 87, 18, 16, 34, 50, 84, 45, 40, 85, 36, 32, 68, 11, 79
and 3 times this sequence.
Then there are 88 0-chains of length 11, and 616 other chains of length 11.

F569= 366844743160809780614736136462756304511005869011952298152702428684177680611935 60857904335017879540515228143777781065869 is a more striking example of an early-appearing prime.

Page 163: The extraordinary property of this sequence is that if p is a prime, the pth number in the series is divisible by p.
Wikipedia article on the Plastic Number
Article by Ian Stewart  