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 p² − 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 p² − 1 steps, i.e. there is a Fibonacci number F_s such that p is a factor of F_s and s ≤ p² − 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 F_s = 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) ≤ p² − 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)... (F_r−1a + F_rb, F_ra + F_r+1b) ... (F_s−2a + F_s−1b, F_s−1a + F_sb)

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 (F_r−1a + F_rb, F_ra + F_r+1b), for r < s. That is, we ask whether there is some number c such that (ca, cb) = (F_r−1a + F_rb, F_ra + F_r+1b) modulo p. This is equivalent to:

a (F_ra + F_r+1b) = b (F_r−1a + F_rb)

which simplifies to F_r (a² + ab − b²) = 0. Since F_r ≠ 0, the possibility of two pairs being proportional arises only if a² + ab − b² = 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 f² = 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)² = 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 p² − 1 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)² = 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.