Crikey Math

Having fun exploring mathematics

  • Home
  • About
  • Blog
  • Contribute
en English
af Afrikaanssq Albanianam Amharicar Arabichy Armenianaz Azerbaijanieu Basquebe Belarusianbn Bengalibs Bosnianbg Bulgarianca Catalanceb Cebuanony Chichewazh-CN Chinese (Simplified)zh-TW Chinese (Traditional)co Corsicanhr Croatiancs Czechda Danishnl Dutchen Englisheo Esperantoet Estoniantl Filipinofi Finnishfr Frenchfy Frisiangl Galicianka Georgiande Germanel Greekgu Gujaratiht Haitian Creoleha Hausahaw Hawaiianiw Hebrewhi Hindihmn Hmonghu Hungarianis Icelandicig Igboid Indonesianga Irishit Italianja Japanesejw Javanesekn Kannadakk Kazakhkm Khmerko Koreanku Kurdish (Kurmanji)ky Kyrgyzlo Laola Latinlv Latvianlt Lithuanianlb Luxembourgishmk Macedonianmg Malagasyms Malayml Malayalammt Maltesemi Maorimr Marathimn Mongolianmy Myanmar (Burmese)ne Nepalino Norwegianps Pashtofa Persianpl Polishpt Portuguesepa Punjabiro Romanianru Russiansm Samoangd Scottish Gaelicsr Serbianst Sesothosn Shonasd Sindhisi Sinhalask Slovaksl Slovenianso Somalies Spanishsu Sudanesesw Swahilisv Swedishtg Tajikta Tamilte Teluguth Thaitr Turkishuk Ukrainianur Urduuz Uzbekvi Vietnamesecy Welshxh Xhosayi Yiddishyo Yorubazu Zulu

A cycle of length 5 for iterated squaring modulo a prime

April 12, 2018 By Gary Ernest Davis

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

http://www.crikeymath.com/wp-content/uploads/2017/09/crikey.wav

 

Filed Under: Uncategorized

Recent Posts

  • Does the DNA test say guilty or not guilty?
  • The Turtleback Diagram for Conditional Probability
  • Numbers that, base 2, are blindingly obviously divisible by 3
  • A mysterious sequence of 1s and 2s
  • Does one have to be a genius to do mathematics? Neither necessary nor sufficient.
  • Alexander Bogomolny
  • Binary disjoints of an integer
  • A cycle of length 5 for iterated squaring modulo a prime
  • The diagonal of the Wythoff array
  • Leonardo Bigollo, accountant, son of Bill Bonacci

Archives

Copyright © 2023 · Dynamik Website Builder on Genesis Framework · WordPress · Log in