# How to compute $\mathbb{Z}_n^*$, the unit group of the integers modulo $n$?

I am trying to wrap my head around calculating residue classes, for example $\mathbb{Z}^*_{12} = [1]...$

Would anyone mind making up an example with a decent explanation. I just wrap my head around things easier seeing the process.

Thanks

-
Note that $\mathbb{Z}_{12}^*$ (the unit group of $\mathbb{Z}_{12}$) consists of the residue classes of $1$, $5$, $7$, and $11$. – Zev Chonoles Apr 2 '13 at 2:47
Yeah I dont really understand how you got that. Do you mind explaining your steps? – Mike Apr 2 '13 at 2:51
Sure, I'd be happy to. Though could you clarify, when you say you're having trouble "calculating residue classes", do you mean specifically with computing the unit group $\mathbb{Z}_n^*$, or more generally, with things like computing $[5]^3$ in $\mathbb{Z}_{12}$. – Zev Chonoles Apr 2 '13 at 2:55
More of computing the unit group. – Mike Apr 2 '13 at 3:12

I'll use your notation of $\mathbb{Z}_n$ for the integers mod $n$, the unit group being $\mathbb{Z}_n^*$, and the residue class of an integer $a$ being denoted $[a]$.

Let's consider the definition of $\mathbb{Z}_n^*$. Something is a unit when it has a multiplicative inverse, so $$\mathbb{Z}_n^*=\{[a]\in\mathbb{Z}_n\mid \text{ there is some }[b]\in\mathbb{Z}_n\text{ such that }[a]\cdot[b]=[1]\}.$$ Note that nothing changes if we instead wrote $$\mathbb{Z}_n^*=\{[a]\in\mathbb{Z}_n\mid \text{ there is some }b\in\mathbb{Z}\text{ such that }[a]\cdot[b]=[1]\}$$ (asking for an equivalence class with a desired property is the same thing as asking for the existence of an integer whose equivalence class has the desired property, since every equivalence class is of course the equivalence class of some integer).

Now recall that $[a]\cdot[b]$ is defined to be $[ab]$ (or, depending on how you've constructed $\mathbb{Z}_n$, this may instead be a fact, not a definition). At any rate, we therefore have that $$\mathbb{Z}_n^*=\{[a]\in\mathbb{Z}_n\mid \text{ there is some }b\in\mathbb{Z}\text{ such that }[ab]=[1]\}.$$ Two equivalence classes $[c]$ and $[d]$ in $\mathbb{Z}_n$ are the same if and only if $c\equiv d\bmod n$, or in other words, when $c-d$ is equal to a multiple of $n$. Thus, $$\mathbb{Z}_n^*=\{[a]\in\mathbb{Z}_n\mid \text{ there is some }b\in\mathbb{Z}\text{ such that }ab-1=kn\text{ for some }k\in\mathbb{Z}\}.$$ Replacing $k$ with its negative, we can instead write $$\mathbb{Z}_n^*=\{[a]\in\mathbb{Z}_n\mid \text{ there is some }b\in\mathbb{Z}\text{ such that }ab+kn=1\text{ for some }k\in\mathbb{Z}\}.$$ Note that, given an integer $a$, if there are such a $b$ and $k$, then $\gcd(a,n)=1$, because any common divisor $h$ of both $a$ and $n$ must divide a linear combination of them, in particular, it must divide $$ab+kn=1.$$ The only positive integer dividing $1$ is $1$, so the $\gcd$ of $a$ and $n$ is 1. In fact, the converse is also true; this is Bezout's identity. Thus, $$\mathbb{Z}_n^*=\{[a]\in\mathbb{Z}_n\mid \gcd(a,n)=1\}.$$

-
I think this is an excellent explanation Zev! – Adrián Barquero Apr 2 '13 at 3:51
Thanks for your kind words, Adrián! – Zev Chonoles Apr 2 '13 at 3:52
Okay, so the problem I am working on is finding the cosets of $(\mathbb{Z}^*_{35})^2$ in $\mathbb{Z}^*_{35}$. My first step is listing all the cosets of $\mathbb{Z}^*_{35}$ which I found to be $[x]$ in [1,2,3,4,6,8,9,11,12,13,16,17,18,19,22,23,24,26,27,29,31,32,33,34]. Am I correct in that regard? Thanks for all the help. – Mike Apr 2 '13 at 3:56
Looks right to me - as long as you got rid of all the multiples of $5$ and $7$, you're good :) – Zev Chonoles Apr 2 '13 at 4:04

The units of $\rm\:\Bbb Z_{12}\:$ are the residue classes coprime to $\,12.\:$ We can compute them by sieving in a way similar to Eratosthenes' prime sieve. Make a list of the residue classes, then successively exclude (cross/grey out) elements $> 1\,$ that divide the modulus, along with all of their multiples. Starting with $\,2,\,$ since $\rm\:2\mid 12\:$ we grey out $\,2\,$ and all its multiples, i.e. all even classes.

$$\begin{array}{}1 & \color{#ccc}2 & 3 & \color{#ccc}4 & 5 & \color{#ccc}6 & 7 & \color{#ccc}8 & 9 & \color{#ccc}{10} & 11\end{array}$$

The next unprocessed number is $\,3,\,$ and $\rm\:3\mid 12,\:$ so we grey out it and its multiples.

$$\begin{array}{}1 & \color{#ccc}2 & \color{#ccc}3 & \color{#ccc}4 & 5 & \color{#ccc}6 & 7 & \color{#ccc}8 & \color{#ccc}9 & \color{#ccc}{10} & 11\end{array}$$

The next unprocessed number is $\,5,\,$ and $\:5\nmid 12,\:$ so we don't grey it out, but move on to the next unprocessed number $\,7,\,$ etc. What remains is $\ 1,\,5,\,7,\,11,\:$ which are all of the units of $\:\Bbb Z_{12}.$

As for why the units (invertibles) are those elements coprime to the modulus $\rm\:m,\:$ this is an immediate consequence of the Bezout identity for the gcd, namely

$$\rm\begin{eqnarray} gcd(a,m) = 1\ \iff\,\ \ 1\, &=&\rm\, j\,a + k\,m \ \ \ for\ \ some\ \ j,k\in\Bbb Z\\ \rm \iff\, \ \ 1\,&\equiv&\rm\, j\,a\ \ (mod\ m)\\ \iff\,\ [1]\! &=&\rm\! [j][a]\ \ in\ \ \Bbb Z_m \end{eqnarray}$$

-
Nice, this is a decent algorithm and much faster than just calculating the gcd for every number $\leq m$. As in Eratosthenes sieve, for each divisor $d$ of $m$ we can start the "greying out" from $d$, then skip to $d^2$ for efficiency (since a divisor $kd$ for $k < d$ has been taken care of by the previous divisors). Also similarly, we only go through divisors $\leq \sqrt{m}$. – spin Apr 2 '13 at 20:16

Since you clarified in a comment below your post, you seem interested in knowing how to determine which elements are in the unit group of $\mathbb Z_{12}$, and perhaps, in general how to compute the elements of any unit group $\mathbb Z_n$:

The unit group of $\mathbb Z_{12}$, denoted $\mathbb Z_{12}^*$, consists of all residue classes of elements $z \in \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11\}$ such that $z$ is relatively prime to $12$, all $z$ such that $\gcd(z, 12) = 1$.

Since the only elements $z \in \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11\}$ that are relatively prime to $12$ are exactly $1, 5, 7, 11$, we have that $$\mathbb Z_{12}^* = \{[1], [5], [7], [11]\}$$ which is usually written simply as $$\mathbb Z_{12}^* = \{1, 5, 7, 11\}$$

In general, for a unit group $\mathbb Z_n^*$, Let $[n-1] = \{1, 2, \cdots, n-1\}$, $$\mathbb Z_n^* = \{z \in [n-1] \mid \gcd(z, n) = 1\}$$

-