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