This question already has an answer here:

Can someone please state the condition and prove it? I haven't been able to find a proof anywhere. Characterization of the generators of non-cyclic multiplicative groups would also be helpful.


marked as duplicate by lulu, Community Feb 29 '16 at 21:54

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ This is called the primitive root theorem, and you can find proofs in just about every textbook and lots of places online. It's a little long to prove here though. As for the characterization of non-cyclic multiplicative groups, for finite Abelian groups at least, you have the fundamental theorem of finite Abelian groups. For the groups $\left(\mathbb{Z}/n\mathbb{Z}\right)^\times$ in particular, the analysis is done using the Chinese remainder theorem. $\endgroup$ – EuYu Feb 29 '16 at 21:45

Let's denote the multiplicitive group of integers mod n by $\left(\frac{\mathbb{Z}}{n\mathbb{Z}}\right)^*$.

$\left(\frac{\mathbb{Z}}{n\mathbb{Z}}\right)^*$ is cyclic iff $n=1,2,4,p^k,$ or $2p^k$ where $p$ is an odd prime and $k>0$.

In general, if $n = p_1^{k_1}\dots p_r^{k_r}$, then by the Chinese Remainder Theorem, $\frac{\mathbb{Z}}{n\mathbb{Z}} \cong \frac{\mathbb{Z}}{p_1^{k_1}\mathbb{Z}} \times \dots \times \frac{\mathbb{Z}}{p_r^{k_r}\mathbb{Z}}$ as rings. You can use this to show that:

$\left(\frac{\mathbb{Z}}{n\mathbb{Z}}\right)^* \cong \left(\frac{\mathbb{Z}}{p_1^{k_1}\mathbb{Z}}\right)^* \times \dots \times \left(\frac{\mathbb{Z}}{p_r^{k_r}\mathbb{Z}}\right)^*$

The $n=1,2,4$ cases can just be done explicitly. The other two follow from the decomposition above.

  • $\begingroup$ Okay, I get that, but I don't think your argument shows that there are no primitive roots mod higher powers of two. $\endgroup$ – Vik78 Feb 29 '16 at 21:59
  • $\begingroup$ You are right. For the case of $n=2^k$ with $k > 2$, The subgroup $\{1, -1, 2^{k-1} + 1, 2^{k-1}-1\} \cong \mathbb{Z}_2 \times \mathbb{Z}_2$. $\endgroup$ – Ken Duna Feb 29 '16 at 22:05

It is cyclic if and only if $n$ has the form $p^k$, $2p^k$, $2$ or $4$ with $p$ odd prime.

This is because if $n=\prod p_i^{n_i}$, then $\mathbb{Z}/n\mathbb{Z}^* \simeq \prod \mathbb{Z}/p_i^{n_i}\mathbb{Z}^*$.

Now if $p$ is odd then $\mathbb{Z}/p_i^{n_i}\mathbb{Z}^* \simeq \mathbb{Z}/p_i^{n_i-1}(p_i-1)\mathbb{Z}$. On the other hand, $\mathbb{Z}/2^k\mathbb{Z}^*$ is already not cyclic if $k>2$, and $\mathbb{Z}/2\mathbb{Z}^* = \{1\}$ while $\mathbb{Z}/4\mathbb{Z}^* \simeq \mathbb{Z}/2\mathbb{Z}$.

Now for the product of cyclic groups to be cyclic, it is necessary and sufficient that they have coprime orders. So the power of 2 cannot exceed $2^2 = 4$, and if $n$ has more than one odd prime factor, there are two groups with even order in the product, which is not allowed.

So you can only get $2$, $4$, $p^k$, $2p^k$ or $4p^k$. Now the last one is excluded because $\mathbb{Z}/4\mathbb{Z}^* \simeq \mathbb{Z}/2\mathbb{Z}$ so it gives to groups with even order. Hence the result.


Not the answer you're looking for? Browse other questions tagged or ask your own question.