# The structure of $(\mathbb{Z} / 72 \mathbb{Z})^*$

I am trying to do the following question in preparation for my number theory exam.

Write down the structure of $G = (\mathbb{Z}/ 72 \mathbb{Z})^*$ as a product of cyclic groups and find a set of generators for $G$.

I have seen a solution to this question and it given as follows. We know $72 = 2^3 \times 3^2$. Thus $G = (\mathbb{Z} /8 \mathbb{Z})^* \times (\mathbb{Z} /9 \mathbb{Z})^*$. We know that $(\mathbb{Z} /8 \mathbb{Z})^* \cong C_2 \times C_2$ and $(\mathbb{Z} /9 \mathbb{Z})^* \cong C_6$ because $\phi(9) = 6$. Therefore as $2$ and $6$ are not coprime, $G \cong C_2 \times C_2 \times C_6$ and we expect to find $3$ generators.

We know that $(\mathbb{Z} / 8 \mathbb{Z})^*$ is generated by $7, 5 \pmod8$ and we easily check that the order of $2 \pmod 9$ in $(\mathbb{Z} /9 \mathbb{Z})^*$ is $6$ so it is the generator of the latter group.

To find the generators for $G$ we use the Chinese Remainder Theorem. For the first generator we want an element that is $7 \pmod 8$ and $1 \pmod 9$. For the second generator we want something that is $5 \pmod 8$ and $1 \pmod 9$. Finally for the last generator we want an element that is $2 \pmod 9$ and $1 \pmod 8$. This gives $a = 37, b=55$ and $c= 65$ respectively.

I don't understand the last paragraph of this solution. How do we know that solving these congruences give generators for $G$?

-
Hint: Think about what the isomorphism $U(\mathbb{Z}_{72})\to U(\mathbb{Z}_8)\times U(\mathbb{Z}_9)$ is. –  Alex Youcis Apr 22 '12 at 2:55
The generators are listed in the wrong order: they should be 55, 37, and 65, respectively. –  Théophile Apr 22 '12 at 3:49

The hint by Alex is exact, but you may rather see it at work. As Theophile remarked, it must be $\,a=55\,,\,b=37\,,\,c=64\,$ , to fit the order you chose, so for example:
$$55=7=-1\pmod 8\Longrightarrow 55^2=1\pmod 8$$ and since $\,55=1\pmod 9\,$, we have that $\,55^2=1\cdot 1=1 \pmod{8\cdot 9=72}\,$ , and this covers the first factor in $\,G = C_2\times C_2\times C_6\,$ . Now just check the same is the same, mutandi mutandis, for the other two factors...(did you spot where we used $\,(8,9)=1\,$ ?)