## The Group of Units (mod n)

The ring $\mathbb{Z}/n\mathbb{Z}$ is more interesting than it is often given credit for.  This post will tell you the isomorphism type of its group of units.

Why care about such a simple thing? Well first, the rings $\mathbb{Z}/n\mathbb{Z}$ are universal, in the following sense. If $R$ is any ring with unity, there exists a unique $n\geq 0$ and injective homomorphism $f: \mathbb{Z}/n\mathbb{Z} \to R$. $n$ here is called the characteristic of $R$. It’s easy to find this homomorphism: there is a natural map $\mathbb{Z}\to R$, and we factor out its kernel (which is of the form $n\mathbb{Z}$, $\mathbb{Z}$ being a principal ideal domain).  So we should expect $\mathbb{Z}/n\mathbb{Z}$ to come up anywhere that rings do (though $n=1$ only applies to a single ring, and $n=0$ is disproportionately common).

Theorem: If $n=2^l \prod_i p_i^{a_i}$, where the product is over odd primes, the group of units $(\mathbb{Z}/n\mathbb{Z})^\times$ can be written as a product of cyclic groups $\prod_i Z_{p^i - p^{i-1}}$ when $l\leq 1$ and $Z_2 \times Z_{2^{l-2}} \times \prod_i Z_{p^i - p^{i-1}}$ when $l\geq 2$. In particular, the group of units is cyclic exactly when $n$ is a power of an odd prime, twice a power of an odd prime, or $4$.

The rest of this post will prove this theorem. First, the Chinese remainder theorem tells us that if $n$ factors into primes as $n=\prod_i p_i^{a_i}$, then $\mathbb{Z}/n\mathbb{Z} \cong \prod_i \mathbb{Z}/p_i^{a_i} \mathbb{Z}$. So we only need to address the question when $n=p^k$ is a power of a prime.

What are the invertible elements in $\mathbb{Z}/p^k \mathbb{Z}$? If $p\bigm| a$, then $p^{k-1} a =0$, so $a$ cannot be invertible. Those who are quick on the draw with the number theory will be able to quickly show that if $p$ does not divide $a$, then $a$ is invertible in $\mathbb{Z}/p^k \mathbb{Z}$. (the standard technique here is to note that $a$ and $p^k$ are relatively prime, so we can choose integers $x$ and $y$ such that $ax + p^k y = 1$)

Since there are $p^{k-1}$ elements divisible by $p$, it follows that $\mathbb{Z}/p^k\mathbb{Z}$ has $p^k-p^{k-1}$ units. (notice that this, along with the Chinese remainder theorem, gives us a nice formula for Euler’s phi function)

Proposition 1: When $p$ is odd, the group of units of $\mathbb{Z}/p^k\mathbb{Z}$ is a cyclic group of order $p^k-p^{k-1}$.

Proof: The case $k=1$ is actually the most difficult. It is a special case of a theorem which says that a finite subgroup of the multiplicative group of any field is cyclic. For a proof of this case, see e.g. here. (I will certainly discuss this topic in detail in a future post)

Suppose that $\sigma$ is a generator for the group of units of $\mathbb{Z}/p \mathbb{Z}$. Then the order of $\sigma\ (\rm{mod}\ p^k)$ is divisible by $p-1$, so it is of the form $p^j (p-1)$. Then $\sigma^{p^j}$ has order $p-1$. We claim that $1+p$ has order $p^{k-1}$, from which it follows that $\tau = \sigma^{p^j} (1+p)$ has order $p^{k-1} (p-1)=p^k -p^{k-1}$.

What we really need to show here is that $(1+p)^{p^{k-2}} - 1$ is divisible by $p^{k-1}$ but not $p^k$. But this is straightforward induction: if $(1+p)^{p^{k-2}} = 1 + a p^{k-1}$ with $a$ not divisible by $p$, then taking $p$-th powers we see that $(1+p)^{p^{k-1}} = 1 + ap^k + (\ldots)p^{k+1}$.

Proposition 2: If $k\geq 3$, the group of units of $\mathbb{Z}/2^k\mathbb{Z}$ is the product of two cyclic groups, one of order $2$, and one of order $2^{k-2}$. If $k\leq 2$, the group of units of $\mathbb{Z}/2^k\mathbb{Z}$ is cyclic.

Proof In fact, we will show that $5$ generates a cyclic group of order $2^{k-2}$ that does not contain $- 1$, an element of order $2$. (there is nothing special about $5$ here—any choice that is $5\ (\rm{mod}\ 8)$ will work) We first show, by induction on $k$, that $5^{2^{k-3}} \equiv 1+2^{k-1}\ (\rm{mod}\ 2^k)$, the case $k=3$ being clear.

For $k\geq 3$, the inductive hypothesis now tells us that $5^{2^{k-3}} \equiv 1+2^{k-1}\ (\rm{mod}\ 2^k)$, so there is some $a\in\{0,1\}$ such that $5^{2^{k-3}} \equiv 1+2^{k-1} + a 2^k\ (\rm{mod}\ 2^{k+1})$. Squaring, we get $5^{2^{k-2}} \equiv 1+2^k\ (\rm{mod}\ 2^{k+1})$.

Since $1+2^{k-1}$ is an element of order $2$, this shows that $5$ generates a cyclic group of order $2^{k-2}$. So we just need to make sure that $-1\not\in \langle 5\rangle$. But a cyclic group can contain at most one element of order $2$, and we have already shown $1+2^{k-1}\in\langle 5\rangle$.

The second statement in the proposition is easily verified.

Exercise: Prove the second sentence of the theorem! (hint: for one direction, use the Chinese remainder theorem for cyclic groups, and for the other, count elements of order $2$)