\(\newcommand{\ZZ}{\Bbb Z} \newcommand{\ZZn}[1]{\ZZ / {#1} \ZZ}\)

One of the most familiar rings is the ring of integers modulo \(n\), often denoted \(\ZZn{n}\). Like all rings, it has an additive structure and a multiplicative one. The additive structure is straightforward: \(\ZZn{n}\) is cyclic, generated by \(1\). In fact, every integer \(a\) coprime to \(n\) is a generator for this group, giving a total of \(\phi(n)\) generators. The multiplicative structure, on the other hand, is far less apparent.

Not all elements of \(\ZZn{n}\) can participate in the multiplicative group, because not all of them have inverses. For example, 4 has no inverse in \(\ZZn{6}\); there’s no integer \(a\) such that \(4a \equiv 1 \pmod 6\). Elements that do have inverses are called units, and we’ll denote the group of units in \(\ZZn{n}\) as \(U_n\).

Since an element \(a \in \ZZn{n}\) is a unit iff \(a\) and \(n\) are coprime, there are \(\phi(n)\) units, where \(\phi\) is the totient function. But the size of the group alone doesn’t nail down the group structure.

For example:

• \(U_5 = \{ 1, 2, 3, 4 \}\):
  • generated by \(2\): \(2^0 = 1\), \(2^1 = 2\), \(2^2 = 4\), \(2^3 = 8 = 3\)
  • also generated by \(3\): \(3^0 = 1\), \(3^1 = 3\), \(3^2 = 4\), \(3^3 = 2\)
  • this group is isomorphic to \(\ZZn{4}\)
• \(U_8 = \{ 1, 3, 5, 7 \}\)
  • every element squares to \(1\)
  • this group is isomorphic to \(\ZZn{2} \times \ZZn{2}\)

Is there a way to find the structure of \(U_n\)?

A versatile theorem from ring theory is the Chinese Remainder Theorem, which (as a special case) says that, for \(m\), \(n\) coprime, the rings \(\ZZn{m} \times \ZZn{n}\) and \(\ZZn{mn}\) are isomorphic. This induces an isomorphism on the units as well (can you see why?).

This means that in order to understand the structure of \(U_n\), we only need to understand \(U_{p^k}\) for all primes \(p\) and positive integers \(k\).

We claim that \(U_{p^k}\) is always cyclic for odd \(p\), but for \(p = 2\), it’s only cyclic when \(k = 1, 2\).

Let \(p\) be an odd prime.

Of course, we start with the simplest case, \(U_p\). Because \(\ZZn{p}\) is a field, its multiplicative group is cyclic (see here for a slick proof).

It is tempting to use this as the base case for an induction on \(k\), but for technical reasons, we need to start our induction at \(k = 2\).

Technical Reasons: Assuming that our claim is true and that \(U_{p^k}\) is indeed cyclic, let’s consider the number of generators as \(k\) increases. Since the number of generators in a cyclic group of size \(m\) is \(\phi(m)\), we have:

From the evidence above, we suspect that if \(g\) is a generator mod \(p\), only \(p-1\) of the \(p\) possible lifts to \(U_{p^2}\) will be generators. This suggests there is one “bad” lift for each generator.

Fortunately, we can find this bad lift explicitly: we claim it’s \(g^p\).

We know that \(g^p \equiv g \pmod{p}\), so \(g^p\) really is a lift of \(g\). And since \(g^{p(p-1)} \equiv 1 \pmod{p^2}\), we know that the order of \(g^p\) is at most \(p-1\) – too small to generate all of \(U_{p^2}\).

If our hunch is true, then this is the only bad lift of \(g\), and so, guided by our suspicions, make the following claim:

Claim: if \(a\) is not a multiple of \(p\), then \(g^p + ap\) is a generator of \(U_{p^2}\).

Proof: Since \(g^p + ap \equiv g \pmod{p}\), it has order \(p-1\) in \(U_p\). This means its order in \(U_{p^2}\) must be a multiple of \(p-1\). Its order must also divide the size of the group, narrowing the possibilities to \(p-1\) and \(p(p-1)\). Thus, to prove that \(g^p + ap\) is a generator, we just have to show it doesn’t have order \(p-1\).

Assume it does, and expand \(1 \equiv (g^p + ap)^{p-1}\) by the binomial theorem:

The terms for \(i \ge 2\) have two or more factors of \(p\) in them, so they get killed, leaving us with

Recalling that \(g^{p(p-1)} \equiv 1\), we get:

For this to be true, we would need to find two factors of \(p\) in \((p-1) g^{p(p-2)} ap\). There’s clearly one factor, from the \(p\), but none of the other terms can provide the second. By contradiction, \(g^p + ap\) must have order \(p(p-1)\) and thus generate \(U_{p^2}\).

Note that there are \(p-1\) choices of \(a\), and so we’ve confirmed our suspicion that every generator mod \(p\) has \(p-1\) good lifts and one bad lift mod \(p^2\).

Now we’re ready for the inductive step.

Let \(k \ge 2\) and \(g\) be a generator of \(U_{p^k}\). We claim \(g\) is also a generator for \(U_{p^{k+1}}\).

Since it’s a generator, it has order \(p^{k-1} (p-1)\) in \(U_{p^k}\), and so its order in \(U_{p^{k+1}}\) must be a multiple of that. This means it is either \(p^{k-1} (p - 1)\) or \(p^k (p - 1)\). We just need to show it isn’t the former.

Let’s try to do a binomial expansion like before. We know that \(g^{p^{k-1} (p-1)} = (g^{p^{k-2} (p-1)})^p\), and that \(g^{p^{k-2} (p-1)} = a p^{k-1} + b\) for some \(b < p^{k-1}\). By Euler’s theorem, \(g^{p^{k-2} (p-1)} \equiv 1 \pmod{p^{k-1}}\) (consider the size of \(U_{p^{k-1}}\)). This means that \(b = 1\). Furthermore, because \(g\) is a generator in \(U_{p^k}\), we know that \(p \nmid a\). So \(g^{p^{k-2} (p-1)} = 1 + a p^{k-1}\) where \(p\) and \(a\) are coprime.

Now we can do our binomial business:

How many factors of \(p\) are in each term?

• \(i = 0, 1\): don’t care.
• \(i \ge 2, i \ne p\): \(1\) from the binomial, and at least \(2(k-1)\) from the power, for a total of at least \(2k-1\). Since \(k \ge 2\), we have \(2k-1 \ge k+1\), and these terms vanish mod \(p^{k+1}\).
• \(i = p\): we lose the factor from the binomial, so we have exactly \(p(k-1)\) factors of \(p\). Since \(p\) is odd, \(p \ge 3\), and for \(k \ge 2\), \(3k-3 \ge k+1\), and this term also vanishes.

So we are left with \(g^{p^{k-1} (p-1)} \equiv 1 + a p^k \pmod{p^{k+1}}\), and since \(a\) isn’t a multiple of \(p\), this shows that \(g\) does not have order \(p^{k-1} (p - 1)\). Thus, \(g\) must be a generator mod \(p^{k+1}\).

By induction, this shows that \(U_{p^k}\) is cyclic for all \(k\).

Note that the above argument almost works for \(p = 2\); the base case goes through, and the inductive step fails only when we look at the last term: when \(p = 2\), we can’t conclude \(p(k-1) \ge k+1\). But this only fails at \(k = 2\), it actually continues to work for \(k \ge 3\). So if there were generators for \(U_8\), then they would lift to generators for \(U_{16}\), and those to \(U_{32}\), and so on. But we just barely fail the jump from \(k = 2\) to \(k = 3\), and this is why \(p = 2\) is different from its odd peers.

Still though, we can modify our argument slightly to derive the structure of \(U_{2^k}\) for \(k \ge 3\). Since \(U_8\) is non-cyclic, there is no chance for any higher \(U_{2^k}\) to be cyclic. But we will show they’re pretty darn close.

We will call \(g\) a “near-generator” of \(U_{2^k}\) if \(g\) generates half the group, and multiplying by \(-1\) gives the other half. Our base case is \(U_8 = \{ 1, 3, 5, 7 \}\), for which \(3\) and \(5\) are near-generators.

Say that \(g\) is a near-generator of \(U_{2^k}\). We claim that it is also a near-generator of \(U_{2^{k+1}}\).

As before, we show the possible orders for \(g\), and eliminate all but one possibility. Since \(g\) is a near-generator mod \(2^k\), it has order \(2^{k-2}\) in \(U_{2^k}\). Thus its order in \(U_{2^{k+1}}\) must be a multiple of \(2^{k-2}\). This leaves possibilities \(2^{k-2}\), \(2^{k-1}\), and \(2^k\). It cannot be \(2^k\), because that would imply that \(U_{2^{k+1}}\) is cyclic, and that is impossible. So it remains to eliminate \(2^{k-2}\).

A similar argument to the odd \(p\) case can be used to tell us that \(g^{2^{k-3}} = 1 + a 2^{k-1}\) for some odd \(a\). Then:

Taken mod \(2^{k+1}\), this tells us that \(g^{2^{k-2}} \equiv 1 + a 2^k \pmod{2^{k+1}}\), eliminating the possibility of \(2^{k-2}\) as the order. Thus, \(g\) must have order \(2^{k-1}\) in \(U_{2^{k+1}}\).

To show that \(-1\) gives the rest of the group, it suffices to show that \(-1\) is not in the half generated by \(g\). But if \(g^r \equiv -1 \pmod{2^{k+1}}\), then surely this would also be true mod \(2^k\), and so this situation does not arise.

Therefore, for \(k \ge 3\), \(U_{2^k} = \{ \pm g^r \mid r = 0, 1, \ldots 2^{k-2} - 1 \} \cong \ZZn{2} \times \ZZn{2^{k-2}}\). The cases of \(U_2\) and \(U_4\) are easily computed to be the trivial group and \(\ZZn{2}\), respectively.

Now we are finally ready to understand \(U_n\) in general: factor \(n\) into primes, and apply the results we learned above.

Specifically, we can answer the question of exactly when \(U_n\) is cyclic.

If \(n\) has two odd prime factors \(p\) and \(q\), then \(n = p^k q^\ell n'\) with \(n'\) coprime to \(p\) and \(q\). So \(U_n \cong U_{p^k} \times U_{q^\ell} \times U_{n'}\). The first two factors in this product have even size, i.e., their sizes have a common factor. This makes it impossible for \(U_{p^k} \times U_{q^\ell}\) to be cyclic, and therefore, \(U_n\) can’t be cyclic either.

If \(8\) divides \(n\), then \(n = 2^k m\) for some odd \(m\) and some \(k \ge 3\), and \(U_n = U_{2^k} \times U_m\). But \(U_{2^k}\) is not cyclic, and this also disqualifies \(n\).

So we are left with \(n = 1\), \(2\), \(4\), \(p^k\), \(2p^k\), and \(4p^k\). The first three can be checked by hand; they’re all cyclic. We showed earlier that \(U_{p^k}\) is cyclic, and the Chinese Remainder Theorem tells us that \(U_{2p^k} \cong U_2 \times U_{p^k}\) is too (note that \(U_2\) is the trivial group). But \(U_{4p^k} \cong U_4 \times U_{p^k}\), and both groups have even size, and so \(U_{4p^k}\) is not cyclic.

To summarize:

• \(U_n\) is cyclic exactly when \(n = 1\), \(2\), \(4\), \(p^k\) or \(2p^k\)
• \(U_{p^k} \cong \ZZn{p^{k-1} (p-1)}\) for odd \(p\)
• \(U_{2^k} \cong \ZZn{2} \times \ZZn{2^{k-2}}\) for \(k \ge 3\)
• lifting a generator always produces another generator, except potentially from \(p\) to \(p^2\) (but the “bad lift” is known explicitly)