The Group of Units (mod n)

The ring $\mathbb{Z}/n\mathbb{Z}$ is more interesting than it is often given credit for. I have also met many advanced students who do not even know, in general, the structure of its group of units. This post will tell you everything you need to know about this structure, which includes a nice result to quote at parties.

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 immediately give up hope of understanding ring theory until we know everything there is to know about $\mathbb{Z}/n\mathbb{Z}$ .

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$ )

About these ads

This entry was posted on Monday, November 24th, 2008 at 8:45 pm and is filed under Uncategorized. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

Notational Notions

The Group of Units (mod n)

Like this:

Leave a Reply Cancel reply

Archives

Blogroll

Essential Reading

Follow “Notational Notions”