2011 October « Theorem of the week

This is something that I was lecturing on the other day. There I was talking to third-year Cambridge undergraduates, who know quite a bit of mathematics about groups and the like, and so I presented the topic accordingly. My challenge in this post is to describe some of the ideas in a way that assumes less technical background, since my aim is wherever possible to make these posts accessible to people who haven’t studied maths at university. I am going to assume that people know a small amount of modular arithmetic, but that’s OK because I’ve written about it previously.

So let’s begin with numerical examples, since one of the nice features of this sort of number theory is that one can get stuck in and try ideas explicitly quite easily (the objects we’re studying are, after all, just natural numbers).

Let’s work modulo 7 (for no particular reason, I just wanted a smallish prime). I’m interested in powers.

For example, modulo 7 the powers of 2 are 1, 2, 4, 1, 2, 4, … (dots because it seems to be repeating).

And the powers of 3 are 1, 3, 2, 6, 4, 5, 1, 3, … (oh, once I get back to 1, I can see that it will keep repeating).

And the powers of 4 are 1, 4, 2, 1, 4, ….

Powers of 5: 1, 5, 4, 6, 2, 3, 1, 5, ….

Powers of 6: 1, 6, 1, 6, … (interesting, I got back to 1 very quickly that time).

Lots of interesting things to explore there.

One observation is that we always seem to get back to 1 at some point. But we know from Fermat’s Little Theorem that this should be the case: we know that $a^{p-1} \equiv 1 \pmod{p}$ , so in this case we were bound to get back to 1 after 6 steps (if not sooner). In this post, I’d like to think about when we get back to 1. In the case of 6, we got back to 1 very quickly; in the case of 3 it took rather longer.

We have a name for this idea, this number of steps it takes to get back to 1. It’s called the order. Officially, the order of the element $a$ modulo $p$ is the least positive integer $d$ such that $a^d \equiv 1 \pmod{p}$ . So the order of 2 modulo 7 is 3, and the order of 3 modulo 7 is 6.

If you know about Lagrange’s theorem about finite groups, then you’ll know that the order of an element divides the order of the group. In our case, we’re looking at the multiplicative group of non-zero integers modulo a prime $p$ , which has order $p-1$ . So the order of $a$ must divide $p-1$ . (In the example above, you can check that the order of each element divides 6.) In this post, I want to concentrate on how many elements have order $d$ , for each divisor $d$ of $p-1$ .