Is the multiplicative group $\Bbb Z_{36}^\times$ cyclic?

Question

I'm trying to answer this question but also understanding a smart method to find if a group like the one mentioned has a cyclic generator or not. I know that similar questions have already been asked but honestly, I did not understand the explanations given. So I decided to ask hoping to better understand with this exercise that I'm trying to solve. Thank you for your understanding.

According to Wikipedia, $\Bbb Z_{36}^\times$ is not cyclic. Now, the multiplciatove group has 12 elements which are 1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35. Of course I need to prove that no one of them could be a generator of $\Bbb Z_{36}^\times$. How can I proceed?

Answer 1

Clearly $1$ is not a generator. To check whether $5$ is a generator, compute a few powers; $$5^1\equiv5,\qquad 5^2\equiv25,\qquad 5^3\equiv17,\qquad5^4\equiv13,\qquad5^5\equiv29,\qquad5^6\equiv1.$$ This already tells you that $5$, $25$, $17$, $13$ and $29$ are not generators. Next do the same for $7$...

Answer 2

It is a classical fact that $\mathbb Z_m^\times$ is cyclic if and only if $m\in\{1,2,4,p^\alpha,2p^\alpha\}$, where $p$ is an odd prime and $\alpha$ is a positive integer.

A simple way to see that $\mathbb Z_{36}^\times$ is not cyclic (which also gives a hint about the proof of the general result) is to observe that for any integer $g$ coprime with $36$, one has $g^6\equiv 1\pmod 9$ and also $g^6\equiv 1\pmod 4$ (in fact, already $g^2\equiv 1\pmod 4$), as it follows by a direct computation or by using Euler's theorem. Therefore $g^6\equiv 1\pmod {36}$, showing that $\mathbb Z_{36}^\times$ does not contain elements of order $|\mathbb Z_{36}^\times|=12$.