The Group of Units (mod n)

November 24, 2008

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)


Fun With Group Actions

November 10, 2008

I had to take a bit of a break to move into my new apartment in the Castro, (which has, incidentally, been a pretty exciting place to live this past week) but now I’m all settled down and ready to tell you about group actions.

The basic idea of a group action is to visualize a group as a set of permutations of some set X, giving a homomorphism \phi: G\to S_{|X|}. A basic example would be the cyclic group Z_n acting on an n-gon by rotation. But here are some more interesting and general group actions for a group G:

  • G acts on G by left multiplication.
  • G acts on a normal subgroup of G by conjugation.
  • G acts on the set of subgroups of G of a fixed order, by conjugation.
  • If H\leq G, G acts on the set of left cosets of H by left multiplication.

All of these can provide useful information through the existence of homomorphisms to some symmetric group S_n. For an example of this technique, let’s consider this classic problem:


Problem: Show that any simple group of order 60 is isomorphic to A_5. (recall that a simple group is one with no nontrivial normal subgroups)

We make use of some basic Sylow theory. Let G be a simple group of order 60 and let k be the number of subgroups of G that have order 5. Sylow’s theorems tell us that k is a factor of 12 and is congruent to 1\ (\rm{mod}\ 5), so k\in \{1,6\}. If k=1, then the group of order 5 is normal, (do you see why?) so k=6.

Let G act on the set of subgroups of G of order 5, by conjugation. This gives a homomorphism \phi: G\to S_6. Because none of these subgroups can be normal (or again appealing to Sylow theory) it is easy to see that \phi\neq 1, so \ker{\phi}\neq G. But \ker{\phi} is a normal subgroup of G, so \ker{\phi}=1 and \phi is injective.

So we can imagine G as a subgroup of S_6. In fact, \phi(G)\leq A_6, as the following lemma will tell us:


Lemma: If H\leq S_n is a simple group of order larger than 2, H\leq A_n.

Proof: Let \sigma: S_n\to Z_2 be the sign homomorphism, so A_n = \ker{\sigma}. Then \ker{\sigma_H} is a normal subgroup of H. But \sigma_H cannot be injective, as |H|>|Z_2|, so \ker{\sigma_H} = H, in other words H\leq \ker{\sigma}=A_n.


Returning to our solution, we can now assume that G\leq A_6. Counting orders, we see that G has index 360/60=6. Let A_6 act on the set of left cosets of G by left multiplication, giving a homomorphism \psi: A_6 \to S_6. Pausing for a moment to verify that \psi\neq 1, the fact that A_6 is simple tells us that \psi is injective, and applying the lemma tells us easily that \psi:A_6\to A_6 is an isomorphism.

What is the image of G under this isomorphism? Well, let’s think about the action again. We have some cosets x_1 G, x_2 G, x_3 G, x_4 G, x_5 G, G. Multiplication on the left by elements of G is certainly not guaranteed to fix the first five, but it will always fix the last one. In other words, \psi(G)\leq S_5. So \psi(G)\leq S_5 \cap A_6=A_5.

Since |G|=|A_5|, it follows that \psi is an isomorphism carrying G to A_5, and we are done.


As we can see, group actions provide an excellent if somewhat magical way of reasoning about finite groups that are too big to be easily understood by hand. Make them part of your group theory toolbox.