The period the golden ratio sets

Write down the Fibonacci numbers and keep only their last digits: 0, 1, 1, 2, 3, 5, 8, 3, 1, 4, 5, 9, 4, … Each digit is the last digit of the sum of the two before it, so the whole sequence of last digits is determined by any two consecutive ones, and since there are only a hundred possible pairs, the sequence must eventually come round to a pair it has seen and repeat for ever. It does so after sixty terms, and it returns to its very beginning, 0 and 1, because the rule can be run backwards as well as forwards. The same is true modulo any whole number $n$: the Fibonacci numbers modulo $n$ repeat with a period, called the Pisano period $\pi(n)$, after Leonardo of Pisa who introduced the sequence.

The periods look erratic: $\pi(2) = 3$, $\pi(3) = 8$, $\pi(5) = 20$, $\pi(7) = 16$, $\pi(11) = 10$, $\pi(13) = 28$. But at the primes they follow a law that is visible at once when they are plotted.

Every dot lies on one of two lines, $p - 1$ or $2(p + 1)$, or on a fraction of one: a half, a third, a quarter. Which line is decided by the prime’s remainder on division by 5. Primes congruent to $\pm 1$ modulo 5 — those ending in 1 or 9 — have periods dividing $p - 1$. Primes congruent to $\pm 2$ — ending in 3 or 7 — have periods dividing $2(p + 1)$, and never dividing $p + 1$. The primes 2 and 5 are exceptions, with periods 3 and 20. This essay explains the law by the field the golden ratio lives in, which is the theme of the polynomial that breaks modulo the primes applied to the simplest interesting polynomial, $x^2 - x - 1$.

Sixty last digits #

The last digits first, because they show how periods combine. A number’s last digit is fixed by its remainders on division by 2 and by 5, so the Fibonacci numbers modulo 10 repeat exactly when they repeat both modulo 2 and modulo 5.

Modulo 2 the sequence is 0, 1, 1, 0, 1, 1, …, with period 3: every third Fibonacci number is even. Modulo 5 the period is 20. The least common multiple of 3 and 20 is 60, and that is the period of the last digits. The zeros come every fifteen terms, so every fifteenth Fibonacci number is divisible by 10; the first is $F_{15} = 610$. In general $\pi(n)$ is the least common multiple of $\pi$ at the prime powers dividing $n$, by the Chinese remainder theorem, so the primes decide everything.

Where the golden ratio lives #

Binet’s formula writes the Fibonacci numbers through the golden ratio:

$$F_n = \frac{\varphi^n - \bar\varphi^n}{\varphi - \bar\varphi}, \qquad \varphi = \frac{1 + \sqrt5}{2}, \quad \bar\varphi = \frac{1 - \sqrt5}{2},$$

where $\varphi$ and $\bar\varphi$ are the two roots of $x^2 = x + 1$. Over the real numbers $\varphi$ is irrational, and the integers of the field it generates are the numbers $a + b\varphi$. To work modulo a prime $p$, the same formula can be used inside a finite field, provided there is a field of characteristic $p$ that contains roots of $x^2 - x - 1$.

There are two cases, and they are the two lines. If $x^2 - x - 1$ has roots among the remainders modulo $p$ — two whole numbers $r$ and $s$ with $r^2 \equiv r + 1$ — then $\varphi$ and $\bar\varphi$ are ordinary elements of the field of $p$ elements. By Fermat’s little theorem, $r^{p-1} \equiv 1$ and $s^{p-1} \equiv 1$, so Binet’s formula repeats after $p - 1$ steps, and the period divides $p - 1$. Modulo 11, for instance, $x^2 - x - 1 = (x - 4)(x - 8)$, and indeed $\pi(11) = 10$.

If $x^2 - x - 1$ has no roots modulo $p$, they must be adjoined: the field of $p^2$ elements contains them, just as the field of real numbers of the form $a + b\sqrt5$ contains $\varphi$ over the rationals. In that larger field the map $z \mapsto z^p$ is an automorphism, the Frobenius, which fixes the remainders modulo $p$ and must send a root of $x^2 - x - 1$ to a root. It cannot fix $\varphi$, since $\varphi$ is not a remainder, so it sends $\varphi$ to its conjugate:

$$\varphi^p = \bar\varphi = 1 - \varphi = -\frac1\varphi.$$

Multiplying by $\varphi$ gives $\varphi^{p+1} = -1$, and squaring gives $\varphi^{2(p+1)} = 1$. The same holds for $\bar\varphi$, so Binet’s formula repeats after $2(p + 1)$ steps, and the period divides $2(p + 1)$. It cannot divide $p + 1$, because $\varphi^{p+1} = -1 \ne 1$.

The minus sign in $\varphi^{p+1} = -1$ has a source worth naming. The product of the golden ratio and its conjugate is $\varphi\bar\varphi = -1$: the golden ratio is a unit of the integers $a + b\varphi$, with norm $-1$, the generator of the one-dimensional lattice of units that units that form a lattice described for quadratic fields. In the field of $p^2$ elements, $\varphi^{p+1} = \varphi \cdot \varphi^p = \varphi\bar\varphi$, which is the norm, and the norm is $-1$ whatever the prime. The factor of two in $2(p + 1)$ is that minus sign. A unit of norm $+1$, such as $2 + \sqrt3$ in its own field, would give periods dividing $p + 1$ instead. The same norm $-1$ is why the golden rectangle that eats itself alternates between too long and too short as it is cut down: the convergents $F_{n+1}/F_n$ overshoot and undershoot $\varphi$ in turn, because $F_{n+1}F_{n-1} - F_n^2 = (-1)^n$.

The table checks this for nine small primes by computing $\varphi^p$ directly, as $a + b\varphi$ with $a$ and $b$ remainders and the rule $\varphi^2 = \varphi + 1$: for 11, 19, 29, 31 and 41 the answer is $\varphi$, and for 3, 7, 13 and 47 it is $1 - \varphi$. Which case occurs is the question whether 5 is a square modulo $p$, since the roots of $x^2 - x - 1$ are $(1 \pm \sqrt5)/2$; and by quadratic reciprocity, 5 is a square modulo an odd prime $p$ exactly when $p$ is a square modulo 5, which means $p \equiv \pm 1$. The last digit of a prime decides its Fibonacci period because reciprocity turns a question about $p$’s arithmetic into a question about 5’s.

This is the simplest case of the census in the essay on how a polynomial breaks modulo the primes, where $x^3 - 2$ splitting in three different ways modulo different primes recorded the structure of its Galois group. For $x^2 - x - 1$ the Galois group has two elements, the identity and the swap of $\varphi$ with $\bar\varphi$, and the Frobenius at $p$ is one or the other: the identity for primes ending in 1 or 9, the swap for primes ending in 3 or 7. The Fibonacci period is the Frobenius made visible.

How long the period actually is #

The law gives a bound, not the period. The period is the order of $\varphi$ in the multiplicative group of its field — or twice or four times that, according to signs — and it can be any divisor of the bound compatible with the case. The index, the bound divided by the period, measures how far short it falls.

For primes below 10,000 the full period is the most common case in both classes: 322 of the 609 primes ending in 1 or 9 have period exactly $p - 1$, and 486 of the 617 ending in 3 or 7 have period exactly $2(p + 1)$. The rest fall short by small factors, mostly two and three for the first class. For the second class the index is always odd — 1, 3, 7, 9, never 2 — because the period cannot divide $p + 1$, so it cannot lose a factor of two. A few primes fall very far short: the period modulo 9349 is only 38, an index of 246, the largest in the range — which is the statement that 9349 already divides $F_{38} = 39{,}088{,}169 = 4181 \times 9349$, a Fibonacci number barely larger than the prime squared.

Whether infinitely many primes have the full period is a question of the same kind as Artin’s conjecture, that 2 is a primitive root modulo infinitely many primes. It is expected, with a predicted density, and proved only under the generalised Riemann hypothesis.

Never more than six times the modulus #

For composite moduli the periods multiply up through the least common multiple, and a simple bound holds for all of them.

Peter Freyd and Kevin Brown proved in 1992 that $\pi(n) \le 6n$ for every $n$, with equality exactly when $n = 2 \cdot 5^k$. The computation shows the bound attained at 10, 50 and 250 and nowhere else up to 1,000. The extreme comes from combining the two most generous moduli: modulo $5^k$ the period is $4 \cdot 5^k$, four times the modulus, because 5 divides the discriminant of $x^2 - x - 1$ and behaves like neither line; and modulo 2 it is 3, a factor of one and a half, which the least common multiple keeps whole because 3 and $4 \cdot 5^k$ share no factor. Most moduli sit far below the bound, and the primes on the lower line sit below 1.

The square of a prime #

Modulo $p^2$ the period is either $\pi(p)$ or $p \cdot \pi(p)$: lifting from $p$ to $p^2$ can only multiply the period by $p$ or leave it alone. It is natural to expect it always to multiply, and every prime ever tested does.

The test does not iterate $p^2$ steps. Fast doubling computes $F_m$ and $F_{m+1}$ modulo $p^2$ in about $\log_2 m$ multiplications, from the identities $F_{2k} = F_k(2F_{k+1} - F_k)$ and $F_{2k+1} = F_k^2 + F_{k+1}^2$, so checking whether $F_{\pi(p)} \equiv 0$ and $F_{\pi(p)+1} \equiv 1$ modulo $p^2$ takes a few dozen multiplications of large integers per prime. For all 1,229 primes below 10,000 the answer is no: the period modulo $p^2$ is $p \cdot \pi(p)$.

D. D. Wall asked in 1960 whether that is always so. A prime where it fails, with $\pi(p^2) = \pi(p)$, is now called a Wall–Sun–Sun prime, after Wall and the brothers Zhi-Hong Sun and Zhi-Wei Sun, who showed in 1992 that the first case of Fermat’s Last Theorem could fail for an exponent $p$ only if $p$ were such a prime. Fermat’s Last Theorem has since been proved by other means, but the question survived it. No Wall–Sun–Sun prime is known; computer searches have gone far beyond the range here; and the heuristic that $F_{\pi(p)}/p$ behaves like a random remainder modulo $p$ predicts that they exist, infinitely many and extremely sparse, about $\log \log x$ of them below $x$.

That is exactly the situation of the two primes where Fermat holds twice, 1093 and 3511, for which $2^{p-1} \equiv 1$ modulo $p^2$ rather than merely modulo $p$. The Wieferich condition is about the order of 2 modulo $p^2$, and the Wall–Sun–Sun condition about the order of $\varphi$; both ask whether a natural number that is 1 modulo $p$ happens to be 1 modulo $p^2$ as well, and both are expected to happen with probability $1/p$ for each prime. For 2 the coincidence has happened twice; for the golden ratio, not yet.

The same period in another disguise #

The surprising connection is with a chaotic map. Arnold’s cat map, which scrambles a picture and then always brings it back, acts on a square grid of pixels by the matrix $\begin{pmatrix}2 & 1\\ 1 & 1\end{pmatrix}$, which is the square of the Fibonacci matrix $\begin{pmatrix}1 & 1\\ 1 & 0\end{pmatrix}$. Its powers contain Fibonacci numbers, and on an $N \times N$ grid the picture returns when those powers are the identity modulo $N$: after half the Pisano period of $N$. A grid of 101 pixels a side, where 101 ends in 1, returns after at most 50 steps; a grid of 103, ending in 3, may need up to 104. The golden ratio’s field decides how long a chaotic map takes to undo itself.

The same arithmetic governs the repeating expansions in the golden-ratio base: a fraction written in base $\varphi$ is eventually periodic, and its period is a Pisano period of the denominator. And it is the reason Fibonacci-based random number generators and hash functions have the cycle lengths they do. In each case the object is a power of the matrix $\begin{pmatrix}1 & 1\\ 1 & 0\end{pmatrix}$, whose eigenvalues are $\varphi$ and $\bar\varphi$, and the period is the order of those eigenvalues in whatever finite field the arithmetic happens to be done in.

Two lines and a scatter, not a formula #

The figures show periods at particular primes, all computed by stepping the sequence until it returns to 0, 1, and they illustrate a law that is proved, not observed: the divisibility of the period into $p - 1$ or $2(p + 1)$ follows from Fermat’s little theorem and the Frobenius, as above. What they cannot show is the period itself as a formula. There is none known: the period at $p$ is the order of $\varphi$ in a finite field, and computing an order needs the factorisation of $p - 1$ or $p + 1$ and some exponentiation, as for any multiplicative order.

The Wall–Sun–Sun figure is a negative search over a small range. It shows that no such prime lies below 10,000; that none exists at all is a conjecture in the other direction — the heuristic says they exist — and no figure of any size could settle it.

Iterated pairs, fast doubling and quoted theorems #

Computed here: the Pisano period of every prime below 10,000 and every modulus up to 1,000, by stepping pairs; the divisibility of each prime’s period into its bound, and the non-divisibility into $p + 1$ for the second class; $\varphi^p$ in the field of $p$ or $p^2$ elements for nine primes, exactly; the bound $6n$ and the moduli attaining it; and the test of $\pi(p^2)$ for all primes below 10,000 by exact fast doubling.

Quoted: Binet’s formula, the theory of finite fields and the Frobenius, quadratic reciprocity (proved in earlier essays), Freyd and Brown’s bound, Wall’s question and the Suns’ theorem, the status of searches for Wall–Sun–Sun primes, and the connection with Artin’s conjecture.

Still open: a Wall–Sun–Sun prime #

Is there a prime $p$ for which the Fibonacci period modulo $p^2$ equals the period modulo $p$? None is known, the heuristics say there are infinitely many, and the expected count below $x$ grows like $\log \log x$, so slowly that a search could run for ever without finding one even if they exist. The analogous question for 2, the Wieferich primes, has two known answers; for the golden ratio there are none, and nothing short of a proof that the remainders are not random can decide it.

A second question is the distribution of the index. The proportion of primes with the full period, and with each smaller period, is predicted by a heuristic of Artin’s kind, refined for the special arithmetic of $\varphi$ — for instance, that its order can never be a factor of two short in the second class. The predicted densities agree with the counts here to within the noise of a range this small; proving them, even for the single statement that infinitely many primes have the full period, requires a hypothesis about the zeros of zeta functions that nobody can currently remove.

The Frobenius made visible #

The Fibonacci numbers modulo a prime $p$ repeat with a period dividing $p - 1$ when 5 is a square modulo $p$ and dividing $2(p + 1)$ when it is not, because the golden ratio then lives in the field of $p$ elements or must be adjoined, and in the second case the $p$-th power map swaps it with its conjugate. Every prime below 10,000 obeys the law, most have the full period, and none has a period modulo $p^2$ shorter than $p$ times its period modulo $p$.

The period of a sequence that schoolchildren write down is set by the Galois theory of $\mathbb{Q}(\sqrt5)$, and the question that remains open about it — whether a Wall–Sun–Sun prime exists — is the golden ratio’s version of the question of Wieferich primes, as stubborn and for the same reason.