Number of generators in $(\mathbb{Z}_m^*, \cdot_m)$?

Question

The group $(\mathbb{Z}_m^*, \cdot_m)$ is the group with elements $$ \{ a \in \{0, 1, ..., m-1\} \mid \gcd(a, m) = 1 \} $$ and $\cdot_m$ is the relation $a\cdot_m b = a \cdot b \mod m$.

How many generators are in the group $(\mathbb{Z}_{100}^*, \cdot_{100})$?

Given that I know that $(\mathbb{Z}_{25}^*, \cdot_{25})$ is cyclic and a subgroup of $(\mathbb{Z}_{100}^*, \cdot_{100})$, I'd say the group $(\mathbb{Z}_{100}^*, \cdot_{100})$ is also cyclic and so must have $\phi(100)$ generators with $\phi(100)$ the Euler $\phi$ function, so there should be $40$ generators.

Answer 1

Note that $gcd(x,100)=1$ implies $$x^{20} \equiv 1 \pmod{25} \\ x^{20} \equiv 1 \pmod{4}$$

By the Chinese Remainder Theorem you then get $$x^{20}\equiv 1 \pmod{100}$$

Since your group has 40 elements, the group cannot be generated by a single element.

Answer 2

Since $100$ is the product of the mutually prime numbers $25$ and $4$, one would expect that $\Bbb Z_{100}^*$ would have the structure of $\Bbb Z_{25}^*\oplus\Bbb Z_4^*$, thus isomorphic to the (additive) group $\Bbb Z_{20}\oplus\Bbb Z_2$.

One may take the generator of $\Bbb Z_{25}^*$ to be $17$, of $\Bbb Z_4^*$ to be $3$. The two separate generators should be $\equiv17\pmod{25}$ and $\equiv1\pmod4$ for the one; and $\equiv1\pmod{25}$ and $\equiv3\pmod4$ for the other. Using Chinese Remainder Theorem, that would be $17$ and $51$ for the two generators.

Answer 3

Along the same lines as @Lubin, the group of units functor respects direct products. Thus we can expect $\Bbb Z_{100}^*\cong(\Bbb Z_{25}\times\Bbb Z_4)^*\cong\Bbb Z_{25}^*\times\Bbb Z_4^*\cong\Bbb Z_{20}\times\Bbb Z_2$, and the latter is not cyclic.

Then looking at @N. S.'s answer, note that the order of an element $(a,b)\in\Bbb Z_{20}\times \Bbb Z_2$ will divide $\operatorname {lcm}(2,20)=20$.