Math Mondays

A work in progress.

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

September 10, 2018

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

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?

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: