27
$\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$
27
$\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$
  • 2
    $\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 '17 at 20:03
  • $\begingroup$ Julien, why doesn't the even prime work please? $\endgroup$ – BCLC Oct 17 '18 at 11:48
10
$\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$
5
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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