Cyclicity Condition for Units of Ring of Integers Modulo m

Theorem

Let $n \in \Z_{\ge 0}$ be a positive integer.

Let $\struct {\Z / n \Z, +, \times}$ be the ring of integers modulo $n$.

Let $U = \struct {\paren {\Z / n \Z}^\times, \times}$ denote the group of units of $\struct {\Z / n \Z, +, \times}$.

Then $U$ is cyclic if and only if either:

$n = p^\alpha$

or:

$n = 2 p^\alpha$

where $p \ge 3$ is prime and $\alpha \ge 0$.

Proof

Sufficient condition

Let $U$ be cyclic.

Let $n \ge 0$ be an integer.

Let $n = p_1^{e_1} \cdots p_r^{e_r}$, be the decomposition of $n$ into distinct prime powers given by the Fundamental Theorem of Arithmetic.

Then by the corollary to the Chinese remainder theorem we have an isomorphism:

$\Z / n \Z \simeq \Z / p_1 \Z \times \cdots \times \Z / p_r \Z$

By Units of Direct Product are Direct Product of Units we have:

$\paren {\Z / n \Z}^\times \simeq \paren {\Z / p_1 \Z}^\times \times \cdots \times \paren {\Z / p_r \Z}^\times$

Suppose that $r \ge 2$, and choose $i, j \in \set {1, \ldots, r}$ such that $i \ne j$.

If $\paren {\Z / p_i \Z}^\times$ or $\paren {\Z / p_j \Z}^\times$ is not cyclic, then $\paren {\Z / n \Z}^\times$ cannot be cyclic.

This article, or a section of it, needs explaining. In particular: Link to a result establishing the above fact. You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by explaining it. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{Explain}} from the code.

Therefore suppose that $\paren {\Z / p_i \Z}^\times$ and $\paren {\Z / p_j \Z}^\times$ are cyclic.

By Order of Group of Units of Integers Modulo m these groups have orders:

$\map \phi {p_i^{e_i} }$

and:

$\map \phi { p_j^{e_j} }$

respectively, where $\phi$ is the Euler $\phi$ function.

By Euler Phi Function of Integer we have:

$\map \phi {p_i^{e_i} } = p_i^{e_i - 1} \paren {p_i - 1}$

and

$\map \phi {p_j^{e_j} } = p_j^{e_j - 1} \paren {p_j - 1}$

If $p_i, p_j$ are odd, $2$ divides $p_i - 1$ and $p_j - 1$.

Therefore $2$ divides $\map \phi {p_i^{e_i} }$ and $\map \phi {p_j^{e_j} }$.

In particular, $\map \phi {p_i^{e_i} }$ and $\map \phi {p_j^{e_j} }$ are not coprime.

Now by Group Direct Product of Cyclic Groups, $\left({\Z / n \Z}\right)^\times$ is not cyclic.

Let $p_i$ or $p_j$ be even.

Without loss of generality, we can assume $p_i = 2$.

Then:

$\map \phi {p_i^{e_i} } = \map \phi {2^{e_i} } = p_i^{e_i - 1} \paren {p_i - 1}$

So if $e_i \ge 2$, then $2$ divides $\map \phi {p_i^{e_i} }$ and $\map \phi {p_j^{e_j} }$.

In particular $\map \phi {p_i^{e_i} }$ and $\map \phi {p_j^{e_j} }$ are not coprime.

Again by Group Direct Product of Cyclic Groups, $\paren {\Z / n \Z}^\times$ is not cyclic.

Thus if $\paren {\Z / n \Z}^\times$ is cyclic, then $n = 2^e \times p^\alpha$ with $e = 0$ or $e = 1$, $\alpha \ge 0$ and $p \ge 3$ prime.

$\Box$

Necessary Condition

This theorem requires a proof. You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by crafting such a proof. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{ProofWanted}} from the code. If you would welcome a second opinion as to whether your work is correct, add a call to {{Proofread}} the page.