It is easy to see with the help of Bezout’s identity that the integers co-prime to n from the set \{0,1,\cdots, n-1\} form a group under multiplication modulo n. This group is denoted by (\mathbb{Z}/n\mathbb{Z})^* and it’s order is given by the Euler’s Totient function: \varphi(n) = |(\mathbb{Z}/p\mathbb{Z})^*| . Gauss showed that (\mathbb{Z}/n\mathbb{Z})^* is a cyclic group if and only if n=1,2,4,p,p^k or 2p^k, where p is an odd prime and k > 0. It is very easy to verify this for n=1,2 and 4, as one can simply list out all positive integers less than and co-prime to n. So, we will only focus on proving that (\mathbb{Z}/n\mathbb{Z})^* is cyclic for the remaining three cases.
Theorem 1: (\mathbb{Z}/p\mathbb{Z})^* is cyclic if p is a prime.
Proof: Let d_1, d_2, \cdots , d_r be all the possible orders of the elements of (\mathbb{Z}/p\mathbb{Z})^*. Let e=\text{lcm}(d_1, d_2, \cdots, d_r) and factor e=p_1^{a_1} p_2^{a_2}\cdots p_k^{a_k} as a product of distinct prime powers. By the definition of \text{lcm}, for each p_i^{a_i} there is some d_j divisible by it. Since the d_j‘s are orders of elements of (\mathbb{Z}/p\mathbb{Z})^*, there is an element x_i whose order is p_i^{a_i} t. Then, the element y_i = x_i^t has order p_i^{a_i}. Hence, y_1 y_2\cdots y_k has order e. Thus, we have found an element of order e. Therefore, e|p-1. But the polynomial x^e-1 has p-1 roots (\text{mod }p). Since \mathbb{Z}/p\mathbb{Z} is a field, any polynomial of degree e cannot have more than e roots. Therefore, p-1\leq e and we deduce that e=p-1. Thus, we have found an element of order p-1.
Theorem 2: (\mathbb{Z}/p^a \mathbb{Z})^* is cyclic for any a\geq 1 if p is an odd prime.
Proof: For a=1, we are done by Theorem 1. Let g be a primitive root (\text{mod }p). We first find a t such that (g+pt)^{p-1}\not\equiv 1 \; (\text{mod }p^2). If g^{p-1}\not\equiv 1 \; (\text{mod }p^2), then we can take t=0. Otherwise, we can choose t=1. Indeed, we have (g+p)^{p-1}\equiv 1+p(p-1) g^{p-2} \not \equiv 1 \; (\text{mod }p^2). Let g+pt have order d\; (\text{mod }p^a). Then, d|p^a (p-1). Since g is a primitive root modulo p, (p-1) | d. So, d=p^{r-1} (p-1) for some r\leq a. We also know that (g+pt)^{p-1} = 1+p s where s \nmid p. Thus, \begin{aligned} (g+pt)^{p(p-1)} &= (1+ps)^{p} \\ &= \sum_{i=0}^{p} \binom{p}{i} (ps)^i \\ &\equiv 1+p^2 s \; (\text{mod }p^3) \end{aligned} By induction, it follows that (g+pt)^{p^{b-1}(p-1)} \equiv 1+p^b s \; (\text{mod }p^{b+1}) Now, g+pt has order d=p^{r-1}(p-1)\; (\text{mod } p^a) which implies (g+pt)^{p^{r-1}(p-1)} \equiv 1 \; (\text{mod }p^a). But then 1+p^r s \equiv 1 \; (\text{mod } p^{r+1}) if r\leq a-1, which implies p | s, a contradiction. Thus, r=a.
Theorem 3: (\mathbb{Z}/2p^a \mathbb{Z})^* is cyclic for any a\geq 1 if p is an odd prime.
Proof: This follows immediately from Theorem 2 and the Chinese remainder theorem.
The fact that (\mathbb{Z}/n\mathbb{Z})^* can be cyclic only for the cases discussed above can also be verified easily using the Chinese remainder theorem.
References
- M. Ram Murty. Problems in analytic number theory. Springer New York, 01-Nov-2008