The organization of units of Z/N

John Goldsmith

download the software that produces these images (runs under Windows) -- see the bottom of this page for usage hints

The integers Z modulo N, for N either prime or composite, hold our interest because they simultaneously have many properties of natural numbers and, at the same time, much structure based on the value of N itself -- its prime decomposition, and that of N-1 and N+1. When N is prime, Z/N is a ring, and every element is a unit, i.e., has a multiplicative inverse; when N is composite, this is no longer true: any n sharing a prime factor with N will fail to have a multiplicative inverse (henceforth, an inverse).

A unit u in Z/N is a number for which there exists an u^-1 so that u* u^-1 = 1. In this note we will observe the relationship between units and their inverses in a visual fashion by looking at the locations of the points (u, u^-1) on a cartesian plane. In (1), we look at the units for Z/N with N = 107, a prime. Throughout this note, the lower left-hand corner of the square is the point (1,1) and the upper right-hand corner is the point (N-1, N-1), and all points (i,j) are solutions to the equation i*j == 1, i.e., i*j = kN + 1, for some integer k. The color of a point (i,j) is determined by the order of i, o(i), which is the least number k such that i^k == 1. Thus two points (i,j) and (k,l) represented in the same color are points for which o(i) = o(k). Since o(i) = o(i ^-1), the order of a point (i,j) on this graphical representation is a sensible notion.

(1)

The three narrow ruled lines in the diagram are the two axes of symmetry ( x=y, x= -y) and the horizontal line y = N/2. There is symmetry about x = y since (i^-1)^-1 = i (so the presence of (i,j) on the graph implies the presence of (j,i)), and in addition, if i*j ==1, then –i * -j == 1, so if (i,j) is a point on the graph, so is (N-i, N-j); it follows that there is a symmetry about x = -y.

To be sure, these symmetries are found regardless of whether N is prime or not; observe some examples in (2) through (6).

(2)

(3)

(4)

(5)

(6)

Let us consider some of the features of these sets. In (3), the units of 119, we see a curve in the lower left hand corner whose points fall on the hyperbola (i,j) such that i*j = 120 = N+1. When N + 1 is highly composite -- that is, the sum of the exponents in N+1's canonical representation as a product of powers of primes is large -- then there will be a large number of ways of factoring N+1 into two numbers i and j such that i*j = N+1.

Similarly, in (4), the units of 121, we see points (i,j) that lie on the hyperbola in the upper left corner. These points are closely related to the points in on the hyperbole in (3): there we looked at the factors of 120 (which was N+1), and here we look at the factors of N-1, which is also 120. In (4), these are points (i,j) such that i * (N-j) = k N + 1, from which it follows that i * j = k' N - 1.

Program usage: Play with the PageUp, PageDown buttons - and the Up arrow and Down arrow; also, the F key. Click on the dots with the mouse, then use the left and right arrows. The PageUp and PageDown buttons will increment and decrement the values of N. You can change the value of N directly by hitting the Backspace key and by typing digits in directly. The code begins to be sluggish after about 3000, and I've put a hard limit around 9000 on permitted input. I'd be happy to send the code to anyone interested (it's currently written in MFC C++). For a given N, the program saves its calculation in memory, so it does not need to recompute, but it doesn't save it from run to run.

Posted June 2004. Home page