Answers to problems:
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^{2} − 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^{2} − 1 steps, i.e. there is a Fibonacci number F_{s} such that p is a factor of F_{s} and s ≤ p^{2} − 1.
The second result sharpens this basic result. Define a 0chain 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 0chain. The number s, the least number such that F_{s} = 0 modulo p, is just the length of the 0chain beginning with (0, 1).
Given a 0chain, there is a class of (p − 1) 0chains obtained by multiplying it by (1, 2, 3,... p − 1). These 0chains are all of the same length s. There are no elements that belong to more than one 0chain, because given any element you can work backwards to find the unique element of form (0, a) which is the initial element of the 0chain. The (p − 1) 0chains account for s(p − 1) distinct pairs. So we have that s(p − 1) ≤ p^{2} − 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−1}a + F_{r}b, F_{r}a + F_{r+1}b) ... (F_{s−2}a + F_{s−1}b, F_{s−1}a + F_{s}b)
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−1}a + F_{r}b, F_{r}a + F_{r+1}b), for r < s. That is, we ask whether there is some number c such that (ca, cb) = (F_{r−1}a + F_{r}b, F_{r}a + F_{r+1}b) modulo p. This is equivalent to:
a (F_{r}a + F_{r+1}b) = b (F_{r−1}a + F_{r}b)
which simplifies to F_{r} (a^{2} + ab − b^{2}) = 0. Since F_{r} ≠ 0, the possibility of two pairs being proportional arises only if a^{2} + ab − b^{2} = 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^{2} = 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 nonproportional pairs. So just as with the 0chains, 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^{2} − 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 p^{2} − 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 0chains.
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 0chains 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 0chains 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 0cycles of length 24.
In contrast, p=89 has s=11, since the 11th Fibonacci number 89 is an example of an unexpectedly earlyappearing 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 0chains of length 11, and 616 other chains of length 11.
F_{569}= 366844743160809780614736136462756304511005869011952298152702428684177680611935 60857904335017879540515228143777781065869 is a more striking example of an earlyappearing prime.
