Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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
up vote 1 down vote accepted

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, mutatis mutandis, for the other two factors...(did you spot where we used $\,(8,9)=1\,$ ?)

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.