Cyclicity Condition for Units of Ring of Integers Modulo n

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 Chinese Remainder Theorem: Corollary we have an isomorphism:

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

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

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

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

Now $\paren {\Z / n \Z}^\times$ has a subgroup

$\set {a \in \paren {\Z / n \Z}^\times:

a \equiv 1\bmod p_k^{e_k}\text{ for all } k \ne i, k \in \set {1, \ldots, r}}$

which is isomorphic to $\paren {\Z / p_i^{e_i} \Z}^\times$.

By Subgroup of Cyclic Group is Cyclic, if $\paren {\Z / p_i^{e_i} \Z}^\times$ or $\paren {\Z / p_j^{e_j} \Z}^\times$ is not cyclic, then $\paren {\Z / n \Z}^\times$ cannot be cyclic.

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

By Order of Group of Units of Integers Modulo n 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, $\paren {\Z / n \Z}^\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.