A cycle of length 5 for iterated squaring modulo a prime

Mercedes McGowen

My colleague Mercedes McGowen has been experimenting with iterated squaring modulo a prime and has, to date, been unable to find a pure cycle of length 5.

Mercedes was originally inspired by A. K. Dewdney’s article “Computer recreations: A computer microscope zooms in for a look at the most complex object in mathematics;”, Scientific American. August, 1985. pp. 16-24 :

“Confronted with infinite complexity it is comforting to take refuge in the finite. Iterating a squaring process on a finite set of ordinary integers also gives rise to interesting structures. The structures are not geometric but combinatorial.”

Roger Heath-Brown

A clue came unexpectedly from a recent arxiv paper of Roger Heath-Brown.

Recall that if $q$ is prime then the multiplicative order of $m\neq 0$ in the field $\mathbb{F}_q$ of integers modulo $q$ is the least integer $k$ such that $m^k \equiv 1 (\textrm{ mod }q)$ .

Heath-Brown remarks (p. 2) that if $f_q:\mathbb{F}_q \to \mathbb{F}_q$ is the squaring map $f(x)=x^2$ then for $0\neq m \in \mathbb{F}_q$ , with odd multiplicative order $r$ , there is a pure cycle of length $k$ for the iterates of $f_q$ where $k$ is the multiplicative order of $2 (\textrm{ mod }r)$ .

So if we want a pure cycle for iterated squaring of length 5 then we choose $r=31$ and seek a prime $q$ for which $\mathbb{F}_q$ has an element of multiplicative order 31.

As one readily checks, through a computational search, the $64^{th}$ prime 311 has this property: namely 265 has multiplicative order 31 in $\mathbb{F}_{311}$ .

The pure cycle of order 5 for the squaring map $f_{311}$ in $\mathbb{F}_{311}$ is $\{265, 250, 300, 121, 24\}$

meaning that $f(265) = 250, f(250) = 300, f(300) = 121, f(121) = 24$ and $f(24) = 265$ .

A further search indicates the same is true for the $74^{th}$ prime 373: a 5-cycle for the squaring map $f_{373}$ in $\mathbb{F}_{373}$ is $\{366, 49, 163, 86, 309\}$ .

In fact there are 6 such 5-cycles for $q=373$ :

$\{12, 111, 144, 221, 351\}$

$\{30, 75, 91, 154, 217\}$

$\{41, 109, 189, 286, 318\}$

$\{49, 86, 163, 309, 366\}$

$\{119, 169, 213, 236, 360\}$

$\{215, 289, 342, 346, 356\}$

Here’s a short list of primes $q$ for which $f_q$ has a 5-cycle in $\mathbb{F}_q$ :

311, 373, 683, 1117, 1303, 1427, 1489, 1613, 1861, 2357, 2543, 2729, 2791, 3163, 3659, 3907, 4093, 4217, 4651, 5023, 5147, 5209, 5333, 5519, 5581, 5953, 6263, 6449, 6883, 7069, 7193, 7937, 8123, 8681, 8867, 8929, 9239, 9859, 10169, 10789, 11161, 11471, 11657, 11719, 12277, 12401, 12959, 13331, 14323, 14447, 14633, 15377, 15439, 15749, 16183, 16369, 16493, 16741, 16927, 17299, …

and these are just primes congruent to 1 mod 31 (OEIS).

Is this, in fact, true: the squaring map $f_q$ has a 5-cycle in $\mathbb{F}_q$ , for $q$ if and only if $q \equiv 1 (\textrm{mod }31)$ ?

Of course when one reflects on it there is nothing special about the number 5: we can find a d-cycle for iterated squaring (mod q), q prime, when $\mathbb{F}_q$ has an element of order $2^d-1$