prove that if $(\mathbb{Z}/n\mathbb{Z})^{*}$ is cyclic, $n=2,4$~or~$p^k, 2p^k$ where $p$ is an odd prime number.

prove that if $(\mathbb{Z}/n\mathbb{Z})^{*}$ is cyclic, $n=2,4$ or $p^k$, $2p^k$ where $p$ is an odd prime number.

I thought of looking at two cases: $n = \Pi p_i^{k_i}$, $n = \Pi 2 p_i^{k_i}$ with $p_i \neq p_j$ if $i \neq j$ and check why these fail to be cyclic.

We see obviously that for both cases $\phi(n) = \Pi (p^{k_i} - p^{k_i - 1})$. this number is even as well because the $p_i$ are odd. Further than this i haven't come.

Any tips and tricks? Am i going to the right direction or is there a better trick in doing this?

HINT: Let $m,n$ be coprime positive integers. Then the Chinese Remainder Theorem says $\mathbb{Z}/mn\mathbb{Z} \cong \mathbb{Z}/m\mathbb{Z} \times \mathbb{Z}/n\mathbb{Z}$.
This implies that $\left(\mathbb{Z}/mn\mathbb{Z}\right)^{\times} \cong \left(\mathbb{Z}/m\mathbb{Z}\right)^{\times} \times \left(\mathbb{Z}/n\mathbb{Z}\right)^{\times}$ so in particular can't be cyclic unless both of these components are cyclic and the orders are again coprime. This should reduce you to the case of prime powers or twice prime powers.
For powers of two, note that $(8k+a)^2 \equiv 1 \mod{8}$ whenever $a$ is odd and use this to construct an argument to why $\mathbb{Z}/2^l\mathbb{Z}$ has no primitive root for $l>2$.
• No - consider $\mathbb{Z}/2\mathbb{Z} \times \mathbb{Z}/2\mathbb{Z}$. – Matt B Sep 23 '15 at 11:35
• I've edited my statement slightly, but if you take $m,n$ to be powers of distinct odd primes then the orders of these groups can't be coprime (they are both divisible by 2) so the product can't be again cyclic in this case. – Matt B Sep 23 '15 at 11:40
• Show that if $a \mod{2^k}$ is a generator for $k>2$ then $a \mod{8}$ is a generator for $(\mathbb{Z}/8\mathbb{Z})^{\times}$ which creates a contradiction. This is why any higher power of 2 cannot have a cyclic unit group since it fails at 8 so must fail for anything larger than 8. – Matt B Sep 23 '15 at 13:37
• This statement is the same as saying that $a^{2^k} = 1 \mod{2^{k+2}}$ for $k>1$ which is a contradiction as the unit group has order $2^{k+1}$, but I think its simpler to use the method I gave above. – Matt B Sep 23 '15 at 14:01