The Chinese Remainder Theorem (CRT) asserts that if \gcd(n,m)=1, \mathbb{Z}/nm\mathbb{Z} is isomorphic to \mathbb{Z}/n\mathbb{Z}\times\mathbb{Z}/m\mathbb{Z}. Thus their unit groups are isomorphic, thus
By the Unique Factorization Theorem (aka Fundamental Theorem of Arithmetic) we only need to describe the structure of (\mathbb Z/n\mathbb Z)^* where n is a prime power.
The Structure Theorem of Finite Abelian Groups
Theorem. If G is a finite abelian group, then there exists an unique sequence d_1,d_2,\cdots d_k where d_i|d_{i+1}, d_1\ne 1, and
G\cong\prod_{i=1}^l C_{d_i}.
This theorem is best proved with module theory.
Proof. See Section 14 of Artin's book Algebra. \square
Primes
Theorem. If p is a prime, then (\mathbb{Z}/p\mathbb{Z})^* is cyclic.
Note that this is equivalent to the existence of a primitive root, an element g that generates the group.
Proof. By the Structure Theorem above, let (\mathbb{Z}/p\mathbb{Z})^* be congruent to
\prod_{i=1}^l C_{d_i}
with d_i as above. Observe that the maximal order of an element is \operatorname{lcm}(d_1,d_2,\cdots,d_l)=d_l. Thus all elements of the group are roots of the polynomial x^{d_l}-1.
But, by Lagrange's Theorem, there are at most d_l solutions to the polynomial above. Thus d_l\ge|(\mathbb{Z}/p\mathbb{Z})^*|=p-1.
Consider the order |(\mathbb{Z}/p\mathbb{Z})^*|. By the isomorphism it is equal to \prod_{i=1}^l d_i, which is in turn \ge d_l. Thus, l=1,d_1=p-1, and we are done. \square
Prime Powers
Theorem. If p is an odd prime, (\mathbb{Z}/p^e\mathbb{Z})^* is cyclic. If p=2, then (\mathbb{Z}/p^e\mathbb{Z})^* is cyclic for e=1,2, and is isomorphic to C_2\times C_{2^{e-2}}.
Corollary. (\mathbb{Z}/n\mathbb{Z})^* is cyclic iff n=1,2,4,p^e,2p^e, where p is an odd prime.