# The Multiplicative Structure of $$\Bbb Z / n \Bbb Z$$

$$\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:

Group # of elements # of generators
$$U_p$$ $$p-1$$ $$\phi(p-1)$$
$$U_{p^2}$$ $$p(p-1)$$ $$(p-1) \phi(p-1)$$
$$U_{p^3}$$ $$p^2(p-1)$$ $$p (p-1) \phi(p-1)$$
$$U_{p^4}$$ $$p^3(p-1)$$ $$p^2 (p-1) \phi(p-1)$$
$$U_{p^k}$$ $$p^{k-1} (p-1)$$ $$p^{k-2}(p-1) \phi(p-1)$$

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:

$$1 \equiv (g^p + ap)^{p-1} \equiv \sum_{i = 0}^{p - 1} \binom{p - 1}{i} (g^p)^{p-1-i} (ap)^i \pmod{p^2}$$

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

$$1 \equiv g^{p(p-1)} + (p-1) g^{p(p-2)} ap \pmod{p^2}$$

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

$$0 \equiv (p-1) g^{p(p-2)} ap \pmod{p^2}$$

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:

$$g^{p^{k-1} (p-1)} = \sum_{i = 0}^p \binom{p}{i} (a p^{k-1})^i$$

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:

$$g^{2^{k-2}} = (g^{2^{k-3}})^2 = (1 + a 2^{k-1})^2 = 1 + 2 \cdot a 2^{k-1} + a^2 2^{2k-2}$$

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)