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 , written , to be the set of invertible elements of with respect to multiplication mod . The size of is then defined to be , Euler’s totient function. It’s pretty immediate that 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 . We’re talking about multiplication, so is also abelian.
For example, has 6 elements, , since
and , since
and none of the other elements of are invertible with respect to multiplication.
It is a nice property, then, that turns out to be the number of numbers less than which are coprime to . Moreover, it is a consequence of the Chinese Remainder theorem that if and are coprime, , so . We can apply this repeatedly to get all the way down to prime powers.
Given this, we only need to understand the value of for prime . There are integers less than , and of these are not coprime to , so . We can now calculate for any . For example, , and .
It is remarkable to me, that for any prime and any positive integer , is cyclic. That is, there is some element such that the elements of the group can be relabeled . Moreover, is cyclic for , and thereafter is isomorphic to . 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,
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 , , we don’t really have a general strategy for finding a generator for it. If we take a particular prime, say , finding a generator isn’t too hard. Applying Lagrange’s theorem to tells us that every element has order dividing 22, so we just need to find an element such that and mod . Thankfully 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 above, our job would have been much harder, since 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.
So while the Cayley table of a cyclic group is in general pretty boring:
the Cayley table of can look pretty interesting, since the columns are jumbled up. The following image is the Cayley table for the prime , which we know corresponds to the group , but it looks nothing like what we might expect:
I’ve generated the following images by finding the invertible elements of 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 and the corresponding 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:
and 997, the largest 3-digit prime number:
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.
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: , and . The rows and columns are just in a different order.
In the following images, I’ve picked out a copy of living in each of and .
Now, some numbers with lots of factors. Let’s start with 24 and 36:
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 , is not cyclic.
A Fermat prime is a prime of the form (or equivalently ). The only known Fermat primes are 3, 5, 17, 257, and 65537. If we have a Fermat prime , we know that . Now the multiplication table for looks like four copies of the one for , which have an additional structure.
Here are 3 and 5:
And here are 8 and 16:
These are 17 and 64:
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):