The Beauty and Joy of Modular Arithmetic

Exploring the Multiplicative Group of Integers Modulo n

This article attempts to provide an interactive exploratory narrative that roughly follows my thought process as I learned about some concepts in number theory. The goal is to provide an explanation that builds upon itself to a satisfying conclusion. This is only an introduction; there are lots of other topics in both mathetmatics and computer science that could be meaningfully connected to modular arithmetic and group theory. With that in mind, I hope you enjoy seeing some of the suprisingly beautiful patterns that arise from some simple mathetmatics!

The Multiplication Table and Hyperbolae

$2 \times 2$ Multiplication Table (Colored by Magnitude)

Remember filling out multiplication tables in elementary school? It's a simple concept—for each empty box, multiply the corresponding row and column numbers... $$\begin{array} {|c|c|}\hline * & \mathbf{1} & \mathbf{2} & \mathbf{3} \\ \hline \mathbf{1} & 1 & 2 & 3 \\ \hline \mathbf{2} & 2 & 4 & 6 \\ \hline \mathbf{3} & 3 & 6 & 9 \\ \hline \end{array}$$ ...and now you have the products of every possible pairing of numbers in the table. A grid of numbers is great and all, but what if we added some color? What does a multiplication table look like when we color each cell brighter based on the magnitude of its number? You probably already have a clear intuition of this, but let's drag this slider and find out! There are a few things to observe here:

It makes a satisfyingly smooth gradient!
The smallest number is always in the top left corner, and the largest number is always in the bottom right corner.
Due to aliasing and imprecision in floating point arithmetic, you may notice Moiré interference patterns appearing as you drag the slider.
The gradient looks like it could be described by a mathematical object—a hyperbola, perhaps?

Let's talk about that fourth observation. Why would a hyperbola appear in multiplication tables? Consider the definition of a hyperbola: $$xy = c$$

In other words, a hyperbola is the set of all points $\left(x, y\right)$ whose product is some constant $c$. Consider the hyperbola defined by $xy = 18$. Looking at the multiplication table for the numbers $0$-$9$, let's highlight every instance of $18$: $$\begin{array} {|r|r|}\hline 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline 2 & 4 & 6 & 8 & 10 & 12 & 14 & 16 & \mathbf{\color{red}{18}} \\ \hline 3 & 6 & 9 & 12 & 15 & \mathbf{\color{red}{18}} & 21 & 24 & 27 \\ \hline 4 & 8 & 12 & 16 & 20 & 24 & 28 & 32 & 36 \\ \hline 5 & 10 & 15 & 20 & 25 & 30 & 35 & 40 & 45 \\ \hline 6 & 12 & \mathbf{\color{red}{18}} & 24 & 30 & 36 & 42 & 48 & 54 \\ \hline 7 & 14 & 21 & 28 & 35 & 42 & 49 & 56 & 63 \\ \hline 8 & 16 & 24 & 32 & 40 & 48 & 56 & 64 & 72 \\ \hline 9 & \mathbf{\color{red}{18}} & 27 & 36 & 45 & 54 & 63 & 72 & 81 \\ \hline \end{array}$$ Although it is admittedly faint, it sure looks like we would see a roughly hyperbolic curve if we were to connect every $\mathbf{\color{red}{18}}$ with a line. In fact, we are generating the positive branches of a whole family of discrete hyperbolae of the form: $$\mathcal{H}_m = \left\{(x, y) \in \mathbb{Z}^2 : xy = m\right\}$$ Using our notation, $\mathcal{H}_{18} = \left\{(2, 9), (3, 6), (6, 3), (9, 2)\right\}$. If a simple multiplication table can already reveal a beautiful underlying patten, what happens if we try the same process with a slightly different operation?

Some Number Theory

Now it's time for a little bit of number theory. Consider the multiplicative group of integers modulo $n$ or, more simply, the group of integers in the range $\left[1, n\right)$ that are coprime to $n$ under multiplication$\mod n$. When we say group, we mean a set paired with a binary operation for which the following are true:

There exists an identity element.
For every element, there exists an inverse.
The group's operation is associative.
The group is closed under its operation.

For example, the integers form a group under addition $\left(\mathbb{Z}, +\right)$:

$m + 0 = m$ for any $m \in \mathbb{Z}$.
$m + (-m) = 0$ for any $m \in \mathbb{Z}$.
$m + (p + q) = (m + p) + q$ for any $m, p, q \in \mathbb{Z}$.
$m + p \in \mathbb{Z}$ for any $m, p \in \mathbb{Z}$.

They do not form a group under multiplication, however, because there exists no multiplicative inverse:

$m * 1 = m$ for any $m \in \mathbb{Z}$.
$m * \frac{1}{m} = 1$ for any $m \in \mathbb{Z}$, but $\frac{1}{m} \notin \mathbb{Z}$.
$m * (p * q) = (m * p) * q$ for any $m, p, q \in \mathbb{Z}$.
$m * p \in \mathbb{Z}$ for any $m, p \in \mathbb{Z}$.

As I'm sure you have guessed by now, the positive integers coprime to (i.e., don't share any factors with) $n$ form a group under multiplication modulo $n$, which I will denote $\left(\mathbb{Z}_n, *_n\right)$, where $*_n$ is "multiplication modulo $n$". For any numbers coprime to $n$, the group axioms hold (note that $\phi\left(n\right)$ is Euler's totient function, which can be though of as a shorthand for $\left|\left(\mathbb{Z}_n, *_n\right)\right|$ in this case):

$m *_n 1 = m$ for any $m \in \mathbb{Z}_n$
$m *_n m^{\phi\left(n\right) - 1} = 1$ for any $m \in \mathbb{Z}_n$
$\left(m *_n p\right) *_n q = m *_n \left(p *_n q\right)$ for any $m, p, q \in \mathbb{Z}_n$
$m *_n p \in \mathbb{Z}_n$ for any $m, p \in \mathbb{Z}_n$

Consider $\left(\mathbb{Z}_6, *_6\right)$: $$\left(\mathbb{Z}_6, *_6\right) = \left\{1, 5\right\}$$ $$\left|\left(\mathbb{Z}_6, *_6\right)\right| = \phi\left(6\right) = 2$$ $$\begin{array} {|r|r|}\hline \mathbf{*_6} & \mathbf{1} & \mathbf{2} & \mathbf{3} & \mathbf{4} & \mathbf{5} \\ \hline \mathbf{1} & 1 & 2 & 3 & 4 & 5 \\ \hline \mathbf{2} & 2 & 4 & \mathbf{\color{red}{0}} & 2 & 4 \\ \hline \mathbf{3} & 3 & \mathbf{\color{red}{0}} & 3 & \mathbf{\color{red}{0}} & 3 \\ \hline \mathbf{4} & 4 & 2 & \mathbf{\color{red}{0}} & 4 & 2 \\ \hline \mathbf{5} & 5 & 4 & 3 & 2 & 1 \\ \hline \end{array}$$

Visually, we can infer from the above modular multiplication table that a number is an element of $\left(\mathbb{Z}_6, *_6\right)$ if its corresponding column does not contain a zero. What does this mean analytically? It is simply the set of all integers $m$ between $0$ and $6$ such that $\gcd\left(m, 6\right) = 1$. If the product of $m$ and any other integer in the same range divides $n$ (as in the zeroes in the table above), then we know $\gcd\left(m, 6\right) \gt 1$. Additionally, we can infer that $6$ is not prime, because $\left\{1, 5\right\} \subsetneq \left\{1, 2, 3, 4, 5\right\}$. It follows that if $n$ is prime, then $\left(\mathbb{Z}_n, *_n\right) = \left\{1, \cdots, n - 1\right\} \iff \phi\left(n\right) = n - 1$. Visually, this means that the modular multiplication table for a prime number contains no zeroes—every positive integer less than $n$ belongs to the multiplicative group of integers modulo $n$.

The Modular Multiplication Table—In Color!

What happens if we color this modular multiplication table like we did with the regular multiplication table? Looking at the table for $\left(\mathbb{Z}_6, *_6\right)$, we can make some predictions:

There appear to be two diagonal lines of symmetry passing through the center of the table—this is reminiscent of of the hyperbolae symmetric about one diagonal in the regular multiplication table.
We might be able to draw an imaginary continuous line connecting all squares of the same value. This is further evidence that there are also hyperbolae embedded in this table.

With these predictions in mind, let's see how the table looks as we increase $n$ by moving this slider . The pattern is rather striking! There are definitely hyperbolae present, but they are now more numerous. Like the regular multiplication table, we can define the hyperbolae: $$\mathcal{H}_{m, n} = \left\{\left(x, y\right) \in \mathbb{Z}^2_n : x *_n y = m\right\}$$ Using $\left(\mathbb{Z}_6, *_6\right)$, we can write $\mathcal{H}_{4,6} = \left\{(4, 1), (2, 2), (5, 2), (1, 4), (4, 4), (2, 5)\right\}$ This set represents the pairs of numbers that, when multiplied modulo $6$, equal $4$. It is important to note that this notation does not reflect that the set is partitioned into four distinct hyperbolae (one on either side of both lines of symmetry).

Try clicking on the modular multiplication table. Clicking on a square will give you the congruence relation that generates that square (i.e., the number that is equivalent to the product of the square's row and column modulo $n$). You could even try to trace out the points for a given $\mathcal{H}_{m,n}$ by picking a value for $m$ and looking for the color that matches that value. Admittedly, this will become pretty difficult as $n$ gets larger, so this exercise is best done for $n \lt 20$ or so.

$3 \times 3$ Modular Multiplication Table (Colored by Magnitude)

Congruence Relation:

$3 \times 3$ Modular Multiplication Table (Colored by Row-Neighbor Proximity)

Average Difference:

One other visually interesting pattern to consider is the proximity of each square to its row-neigbors. In other words, for some square at $(x, y) \in \mathbb{Z}_n$, how close is it to $(x - 1, y)$ and $(x + 1, y)$ on average? We can apply a similar coloring rule where lighter/greener values are more different from their neighbors and darker/redder values are less different from their neighbors. Try dragging this slider to see the pattern in action. Here are two distinct sub-patterns to observe:

In the "foreground", we can see what I will call "discrete boundary hyperbolae". Because the color of each square is still ultimately a function of its magnitude, some hyperbolae are still visible. However, we are only seeing hyperbolae along the boundaries where the result of the product modulo $n$ "rolls over"—where the difference between two neighboring squares is the greatest.
In the "background", we can see a smooth gradient that slowly increases in magnitude as it approaches the center along the $y$-axis. Along each background row, the row-neighbor difference remains constant (excluding the edges, where one neighbor is defined to be either $0$ or $n$).

Conclusion