46
$\begingroup$

When can we say a multiplicative group of integers modulo $n$, i.e., $U_n$ is cyclic?

$$U_n=\{a \in\mathbb Z_n \mid \gcd(a,n)=1 \}$$

I searched the internet but did not get a clear idea.

$\endgroup$
0

3 Answers 3

38
$\begingroup$

So $U_n$ is the group of units in $\mathbb{Z}/n\mathbb{Z}$.

Write the prime decomposition $$ n=p_1^{\alpha_1}\cdots p_r^{\alpha_r}. $$

By the Chinese remainder theorem $$ \mathbb{Z}/n\mathbb{Z}=\mathbb{Z}/p_1^{\alpha_1}\mathbb{Z}\times\ldots\times\mathbb{Z}/p_r^{\alpha_r}\mathbb{Z} $$ so $$ U_n=U_{p_1^{\alpha_1}}\times\ldots\times U_{p_r^{\alpha_r}}. $$

For powers of $2$, we have $$ U_2=\{0\} $$ and for $k\geq 2$ $$ U_{2^k}=\mathbb{Z}/2\mathbb{Z}\times \mathbb{Z}/2^{k-2}\mathbb{Z}. $$

For odd primes $p$, $$ U_{p^\alpha}=\mathbb{Z}/\phi(p^\alpha)\mathbb{Z}=\mathbb{Z}/p^{\alpha-1}(p-1)\mathbb{Z}. $$

So you see now that $U_n$ is cyclic if and only if $$ n=2,4,p^\alpha,2p^{\alpha} $$ where $p$ is an odd prime.

Here is a reference.

$\endgroup$
5
  • 4
    $\begingroup$ Why is it true that $U_{p^\k}=\mathbb{Z}/2\mathbb{Z}\times\mathbb{Z}/2^{k-2}\mathbb{Z}$? $\endgroup$
    – Rasputin
    Jan 20, 2017 at 20:03
  • $\begingroup$ Julien, why doesn't the even prime work please? $\endgroup$
    – BCLC
    Oct 17, 2018 at 11:48
  • $\begingroup$ By equal to symbol $=$ in proof. Did you mean isomorphic? $\endgroup$ Jan 10, 2020 at 14:59
  • $\begingroup$ Why is it true that $U_{p^\alpha} = \mathbb{Z} / p^{\alpha -1} (p-1) \mathbb{Z}$? $\endgroup$ Jul 30, 2021 at 17:36
  • $\begingroup$ UPD nevermind, I found the answer math.stackexchange.com/questions/1387378/ $\endgroup$ Jul 31, 2021 at 12:31
16
$\begingroup$

$U_n$ is cyclic iff $n$ is $2$, $4$, $p^k$, or $2p^k$, where $p$ is an odd prime.

The proof follows from the Chinese Remainder Theorem for rings and the fact that $C_m \times C_n$ is cyclic iff $(m,n)=1$ (here $C_n$ is the cyclic group of order $n$).

The hard part is proving that $U_p$ is cyclic and this follows from the fact that $\mathbb Z/p$ is a field and that $n = \sum_{d\mid n} \phi(d)$.

Any book on elementary number theory has a proof of this theorem. See for instance André Weil's Number theory for beginners, Leveque's Fundamentals of Number Theory, and Bolker's Elementary Number Theory.

$\endgroup$
0
6
$\begingroup$

Here "cyclic if and only if $\varphi(n)=\lambda(n)$" but there's no proof - the proof is elementary but very tricky.

$\endgroup$

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