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)


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: