Beauty in Mathematics: Modular Multiplication Tables

1504801956.png

I’ve thought about number theory an awful lot recently, in preparation for the beginning of term, when I’ll be taking a 24 lecture course on it. So when I woke up this morning with a very strong desire to create something beautiful, it seemed natural to try to work with some of the number theoretic ideas I’ve been exploring.

It’s hard to know at what level to pitch this post since I think that anybody would be able to enjoy these pictures, but I also want to talk about group theoretic concepts where necessary. If you find yourself a little lost, I encourage you to gloss over the technical parts, as there still should be plenty for you to enjoy. If you’re keen, the Wikipedia articles on modular arithmetic and group theory are pretty good.

Multiplicative Groups and Euler’s Totient Function

We define the multiplicative group mod n, written (\mathbb{Z}/n\mathbb{Z})^{\times}, to be the set of invertible elements of \mathbb{Z}/n\mathbb{Z} with respect to multiplication mod n. The size of (\mathbb{Z}/n\mathbb{Z})^{\times} is then defined to be \phi(n), Euler’s totient function. It’s pretty immediate that (\mathbb{Z}/n\mathbb{Z})^{\times} really is a group. Associativity, inverses, and identity come for free, so all we really need to worry about is closure, but that’s provided by the fact that (ab)^{-1} \equiv b^{-1} a^{-1} \mod n. We’re talking about multiplication, so (\mathbb{Z}/n\mathbb{Z})^{\times} is also abelian.

For example, (\mathbb{Z} / 7 \mathbb{Z})^{\times} has 6 elements, 1, 2, 3, 4, 5, 6, since

1 \times 1 \equiv 1 \mod 7 \\ 2 \times 4 \equiv 1 \mod 7 \\ 3 \times 5 \equiv 1 \mod 7 \\ 6 \times 6 \equiv 1 \mod 7

and \phi(8) = 4, since

1 \times 1 \equiv 1 \mod 8 \\ 3 \times 3 \equiv 1 \mod 8 \\ 5 \times 5 \equiv 1 \mod 8 \\ 7 \times 7 \equiv 1 \mod 8

and none of the other elements of \mathbb{Z} / 8 \mathbb{Z} are invertible with respect to multiplication.

It is a nice property, then, that \phi(n) turns out to be the number of numbers less than n which are coprime to n. Moreover, it is a consequence of the Chinese Remainder theorem that if m and n are coprime, (\mathbb{Z} / mn \mathbb{Z})^{\times} \cong (\mathbb{Z} / m \mathbb{Z})^{\times} \times(\mathbb{Z} / n \mathbb{Z})^{\times}, so \phi(mn) = \phi(m)\phi(n). We can apply this repeatedly to get all the way down to prime powers.

Given this, we only need to understand the value of \phi(p^k) for prime p. There are p^k - 1 integers less than p^k, and p^{k-1} - 1 of these are not coprime to p^k, so \phi(p^k) = (p^k - 1) - (p^{k-1} - 1) = p^{k-1} (p - 1). We can now calculate \phi(n) for any n. For example, \phi(91) = \phi(7)\phi(13) = 6 \times 12 = 72, and \phi(504) = \phi(2^3)\phi(3^2)\phi(7) = 4 \times 6 \times 6 = 144.

Cyclic Groups

It is remarkable to me, that for any prime p > 2 and any positive integer k(\mathbb{Z} / p^k \mathbb{Z})^{\times} is cyclic. That is, there is some element a such that the elements of the group can be relabeled 1, a, a^2, \dots, a^{\phi(p^k) - 1}. Moreover, (\mathbb{Z} / 2^k \mathbb{Z})^{\times} is cyclic for k = 1, 2, and thereafter is isomorphic to C_2 \times C_{2^{k-2}}. The proofs of these facts are a little technical but not really too difficult.

We know enough now to completely classify the multiplicative groups up to isomorphism. For example,

\begin{array}{c}(\mathbb{Z} / 175 \mathbb{Z})^{\times} \cong (\mathbb{Z} / 5^2 \mathbb{Z})^{\times} \times (\mathbb{Z} / 7 \mathbb{Z})^{\times} \cong C_{20} \times C_{6} \\ (\mathbb{Z} / 504 \mathbb{Z})^{\times} \cong (\mathbb{Z} / 2^3 \mathbb{Z})^{\times} \times (\mathbb{Z} / 3^2 \mathbb{Z})^{\times} \times (\mathbb{Z} / 7 \mathbb{Z})^{\times} \cong C_{2} \times C_{2} \times C_{6} \times C_{6} \end{array}

At this point, it feels like we’re sort of done with multiplicative groups. Cyclic groups are exactly the simplest type of group possible, and every multiplicative group is a direct product of cyclic groups. Thankfully, multiplicative groups have one trick up their sleeve which make them interesting.

Generators of Multiplicative Groups

It turns out that, although we know that for a prime p(\mathbb{Z} / p \mathbb{Z})^{\times} \cong C_{p-1}, we don’t really have a general strategy for finding a generator for it. If we take a particular prime, say 23, finding a generator isn’t too hard. Applying Lagrange’s theorem to (\mathbb{Z} / 23 \mathbb{Z})^{\times} tells us that every element has order dividing 22, so we just need to find an element a such that a^2 \not\equiv 1 and a^{11} \not\equiv 1 mod 23. Thankfully a = 2 works, and we’re done.

However, things didn’t have to work out so nicely. We currently don’t know very much at all about the relationship between the prime factorisations of consecutive integers (apart from trivial facts like that one contains a 2, and neither factorisation shares the same prime). If we’d picked, say p = 181 above, our job would have been much harder, since p - 1 = 2^2 3^2 5 has 18 divisors.

There are a couple of tricks you can use to speed up the search, but even the best techniques are really not all that much more sophisticated than the above and are still dependent on the particular prime you choose.

It may come as some solace to find out that if you just pick at random, you have a pretty good chance of getting a generator – half of the elements of the group are generators.

Cayley Tables

So while the Cayley table of a cyclic group is in general pretty boring:

CyclicGroupTable_1001

the Cayley table of (\mathbb{Z} / p \mathbb{Z})^{\times} can look pretty interesting, since the columns are jumbled up. The following image is the Cayley table for the prime 19, which we know corresponds to the group C_{18}, but it looks nothing like what we might expect:

19-raw

I’ve generated the following images by finding the invertible elements of (\mathbb{Z} / n \mathbb{Z})^{\times} and forming a multiplication table out of them. The numbers are arranged in order of size along the rows and columns, and the colour of a particular square represents the size of the product – the darker it is, the bigger.

For example, here’s the Cayley table for (\mathbb{Z} / 8 \mathbb{Z})^{\times} and the corresponding numbers:

8.png

Let’s explore.

Prime Numbers

I have sat and thought about what to write in this paragraph for some time, but I just can’t explain how I feel about the following pictures in words. I’ll try. I find these patterns incredibly beautiful. They have so much internal symmetry. In some sense, they are random, but in another, they are exactly what they always had to be. There is no universe where these tables look any different from the ones below. The pictures which follow are exactly why I love mathematics so much, and I hope that you can appreciate their elegance despite my inability to tell you exactly what about them it is that I like.

Here are the multiplication tables for the primes 3, 7, 13, and 19.

As we get higher and higher up, more and more interesting patterns emerge. Here is the table for the prime 113:

113-raw.png

and 997, the largest 3-digit prime number:

997-raw.png

Here’s one for 9973, the largest 4-digit prime number. It’s a largish file (18MB), so be warned. Your monitor might struggle to give you a good impression of what it looks like.

Composite Numbers

Perhaps the only tables more beautiful than the ones for the primes are the ones for the composites. Here’s 105 sandwiched between the primes 103 and 107.

Here are 15 and 16:

At first glance, they appear completely different to each other, but they are not. No: (\mathbb{Z} / 15 \mathbb{Z})^{\times} \cong (\mathbb{Z} / 3 \mathbb{Z})^{\times} \times (\mathbb{Z} / 5 \mathbb{Z})^{\times} \cong C_{2} \times C_4, and (\mathbb{Z} / 16 \mathbb{Z})^{\times} = (\mathbb{Z} / 2^4 \mathbb{Z})^{\times} \cong C_{2} \times C_{4}. The rows and columns are just in a different order.

In the following images, I’ve picked out a copy of C_4 living in each of (\mathbb{Z} / 15 \mathbb{Z})^{\times} and (\mathbb{Z} / 16 \mathbb{Z})^{\times}.

Now, some numbers with lots of factors. Let’s start with 24 and 36:

Here’s 120:

120.png

These start to look pretty crazy pretty quickly. Here are 1260, 2520, and 27720 (35MB).

Powers of Two and Fermat Primes

The last few pictures I want to share with you are related to powers of two. As I mentioned before, the powers of two don’t follow quite the same pattern as the other primes, since for k > 3, (\mathbb{Z} / 2^k \mathbb{Z})^{\times} \cong C_{2} \times C_{2^{k-2}} is not cyclic.

A Fermat prime is a prime of the form 2^n + 1 (or equivalently 2^{2^k} + 1). The only known Fermat primes are 3, 5, 17, 257, and 65537. If we have a Fermat prime p = 2^n + 1, we know that (\mathbb{Z} / p\mathbb{Z})^{\times} C_{2^{n}}. Now the multiplication table for 2^{n+2} looks like four copies of the one for p, which have an additional C_2 structure.

Here are 3 and 5:

And here are 8 and 16:

These are 17 and 64:

And here’s 1024. I’m sure you can imagine what 257 must look like.1024-raw.png

Conclusion

I hope you’ve enjoyed this foray into modular arithmetic. I’m sure there are many, many more interesting things to notice than the brief comments that I’ve made above. As such, if you would like me to post particular images, do mention them in the comments and I’ll provide them.

I’ll leave you with one of my favourites (48):

48-raw.png

2 thoughts on “Beauty in Mathematics: Modular Multiplication Tables

  1. Appears that the last sentence in the following is incomplete
    It turns out that, although we know that for a prime p, (\mathbb{Z} / p \mathbb{Z})^{\times} \cong C_{p-1}, we don’t really have a general strategy for finding a generator for it. If we take a particular prime, say 23, finding a generator isn’t too hard. Applying Lagrange’s theorem to (\mathbb{Z} / 23 \mathbb{Z})^{\times} tells us that every element has order dividing 22, so we just need to find an element a such that a^2 \not\equiv 1 and a^{11} \not\equiv 1 mod 23. Thankfully a = 2 works, and we’re done.However, things didn’t have to work out so nicely. As far as we’re currently aware, the prime

    Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s