Introduction

A set of integers modulo M can be naturally laid out along a circle: (x, y) = (Cos(τ i / M), Sin(τ i / M)). The relationships between the numbers can then be represented as chords. This simple technique is remarkably good at revealing nontrivial patterns. In this post, I will present some visualizations of various modular arithmetics concepts. A huge thanks goes to Christopher Walsh for introducing me to various applications of the circle mapping. For more examples, you can visit Simon Plouffe's home page which has many images of modulo distributions of various integer sequences.

Modular multiplicative inverses

A number b is called a modular multiplicative inverse of a modulo M if (a b) mod M = 1. Only numbers coprime to M have an inverse. They are counted by Euler totient function φ(M) (A000010). The following image was created by connecting each number with its inverse for M = 1 .. 264. Inverses of themselves are marked with radial strokes (A060594 gives their total number). The number of rows, 12, was chosen intentionally. Numbers with many factors (such as in rows 6 and 12) have relatively few lines, and prime numbers > 3 having the most lines can only be found in rows 1, 5, 7, 11.

Primitive roots

g is a primitive root modulo M if every number from 1 to M coprime with M can be expressed as an integer power of g mod M. Primitive roots exist for M = 1, 2, 4, pk and 2pk, where p is an odd prime (A033948). The number of primitive roots, if any exist, is φ(φ(M)) (A010554). Once a single g is known, the rest of them can be found by raising g to powers less than φ(M) and coprime with it.

Following images depict the sequences gk for various M by connecting their consecutive values with chords. Only prime moduli are shown because they are the most interesting in the sense of having all the numbers 1 .. M - 1 representable as gk. Each row starts with the smallest primitive root and continues with its powers that are also primitive roots. Only the first half of all g is shown because the rest of them are multiplicative inverses of the first half and generate the same sequences but in reverse order. Cases M = 127 and M = 257 are shown separately.

Primitive roots mod 127
Primitive roots mod 127
Primitive roots mod 257

Random number generators

Primitive roots are employed in Lehmer random number generators whose output consists of consecutive powers of g: Xi + 1 = g Xi mod M. Circle mapping can be used to spot nonrandomness in such generators. To improve the discriminating power, the visualization has been modified so that the chord color is dependent on the sequence term succeeding the ones connected. The images depict the infamous RANDU RNG (M = 231, g = 216 + 3, A096555) and the one used in ZX81 Sinclair (M = 216 + 1, g = 75 [1]). M used in RANDU has no primitive roots, so the sequence period is only 229. Instead of a uniformly gray disk, RANDU produces a clearly visible pattern. ZX81 RNG looks more uniform, but a wave-like pattern is still visible.

RANDU
ZX81

Permutation polynomials

A polynomial f(x) is a permutation polynomial if it permutes the integers 0 .. M - 1. A characterization of permutation polynomials modulo prime powers can be found in [2]. For example, 2x2 + x is a permutation polynomial for M being a power of 2. I won't try to cover permutation polynomials systematically in this post and will just show a few nice-looking ones. As before, the images are obtained by connecting consecutive values of f(x). Note a curious feature: images for the larger moduli seem to contain smaller versions of the images for the smaller moduli.

Permutation polynomial
Permutation polynomial
Permutation polynomial
Permutation polynomial

References

  1. Steven Vickers. Sinclair ZX81 BASIC Programming.
  2. Rajesh P Singh, Soumen Maity. Permutation Polynomials modulo pn.