## Theorem 38: There is a primitive root modulo a prime

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$.

At this point you might like to go and try some more examples, to make some conjectures before you read on.

OK, got some conjectures?

I (perhaps, I must admit, with the benefit of knowing the answer), would like to draw your attention to two possible conjectures.  These are both about orders in the group under multiplication modulo the odd prime $p$.

• There is at least one element of order $p-1$.
• For each divisor $d$ of $p-1$, there are exactly $\phi(d)$ elements of order $d$ (where $\phi$ denotes the Euler totient function).

It turns out that these facts are both true.  The former is a consequence of the latter (the latter tells us that there are $\phi(p-1)$ elements of order $p-1$, and this is at least 1).  One strategy for proving the former is in fact to prove the latter, even though the second statement appears much stronger and so presumably harder to prove.  This is the approach that I took in my lecture the other day.

In this post, I’m going to skip the proof, but instead take a moment longer to describe the implications of the result.  If $a$ has order $p-1$ modulo $p$, then the powers $1$, $a$, $a^2$, …, $a^{p-2}$ are all different.  So they must be the $p-1$ elements of the multiplicative group modulo $p$.  This is really useful, because it gives us another way to think about those elements (as opposed to 1, 2, 3, …, $p-1$, for example), and sometimes that turns out to be rather convenient.

In group theory terms, we say that $a$ generates the group, and that the multiplicative group modulo $p$ is cyclic.  In number theory terms, we say that $a$ is a primitive root modulo $p$.  I have just realised that I haven’t yet officially stated a theorem in this post.

Theorem Let $p$ be a prime.  Then there is a primitive root modulo $p$.  That is, there is an $a$ with order $p-1$.

Are there primitive roots for every modulus?  No!  I’ll let you experiment a bit to find an example of a modulus where there are no primitive roots.  But it turns out that if $p$ is an odd prime then there is a primitive root modulo any power of $p$, and thanks to the Chinese Remainder Theorem this gets us a long way.

Lots of introductory number theory books discuss this, including Davenport (The Higher Arithmetic), Baker (A concise introduction to the theory of numbers), Jones and Jones (Elementary Number Theory), and so on.  And of course there’s a Wikipedia page.

### 3 Responses to “Theorem 38: There is a primitive root modulo a prime”

1. Number Theory: Lecture 4 « Theorem of the week Says:

[…] Theorem 15: Let be a prime.  Then the multiplicative group is cyclic.  That is, there is some element so that the numbers , , , …, give the whole group.  We call such an element a primitive root modulo .  (Quick check: find all the primitive roots modulo 11, for example.  Try to do this with as little work as possible!  Can you say anything interesting about which primes have many primitive roots and which have only a few?)  We proved this by showing that in , for each divisor of there are exactly elements of order . […]

2. Theorem 39: Euler’s criterion « Theorem of the week Says:

[…] approach would be to make the most of the last Theorem of the Week, which tells us that there is a primitive root modulo .  That is, there is some such that each […]

3. Number Theory: Lecture 4 | Theorem of the week Says:

[…] Theorem 15: Let be prime.  Then the multiplicative group is cyclic.  We proved this by showing that there are exactly elements of order , for each divisor of . […]