Let $n$ be a given arbitrary positive integer, and let $U_n$ denote the group of all the positive integers less than $n$ and relatively prime to $n$ under multiplication mod $n$. Then for which values of $n$ is $U_n$ a cyclic group? And for any such $n$, which elements of $U_n$ generate it?

  • 1
    $\begingroup$ Exactly when $\;n=1\,,\,n=2\,,\,n=2p\,,\,p^k\;$ , with $\;p\;$ an odd prime. $\endgroup$ – DonAntonio Apr 2 '14 at 11:05
  • $\begingroup$ This would have been better if you include "I think" with "which, when" rather with only "which,when"... $\endgroup$ – user87543 Apr 2 '14 at 11:06
  • $\begingroup$ This is explained in almost all books on number theory. $\endgroup$ – lhf Apr 2 '14 at 11:06
  • $\begingroup$ Ihf, I'd appreciate if you could also give an exact reference where both parts of my question are answered. $\endgroup$ – Saaqib Mahmood Apr 2 '14 at 12:04
  • 1
    $\begingroup$ The problem of finding a generator for, say, $U_p$, when $p$ is a (large) prime, is not easy. There's no simple formula for it. $\endgroup$ – Gerry Myerson Apr 2 '14 at 12:26

One key step in this problem is the fact that $U_{ab} \cong U_a \times U_b$, when $a$ and $b$ are co-prime. This comes from the Chinese Remainder Theorem.

The order of $U_a$ is $\phi(a)$ and the order of $U_b$ is $\phi(b)$. In most cases, both $\phi(a)$ and $\phi(b)$ are even and so $m=lcm(\phi(a),\phi(b))<\phi(a)\phi(b)=\phi(ab)$ is an exponent for $U_{ab}$, in the sense that $x^m =1$ for all $x\in U_{ab}$. This proves that $U_{ab}$ is not cyclic.

The remaining cases, when $n$ cannot be written as $n=ab$ with $a,b$ co-prime and $\phi(a),\phi(b)$ both even, give you the direction to the solution.

  • $\begingroup$ Instead of gcd, you mean lcm, I think. $\endgroup$ – Saaqib Mahmood Apr 2 '14 at 11:58
  • $\begingroup$ But $U_{18}$ IS cyclic although $18 = 2 \times 9$ and gcd($2, \ , 9$) $=1$. $\endgroup$ – Saaqib Mahmood Apr 2 '14 at 12:00
  • 1
    $\begingroup$ @SaaqibMahmuud, thanks for the correction. In the example you gave, $\phi(2)$ is not even. $\endgroup$ – lhf Apr 2 '14 at 12:01
  • $\begingroup$ Ihf, can you please write out a complete proof for me? I'm rather rusty on even the elementary number theory! $\endgroup$ – Saaqib Mahmood Apr 2 '14 at 12:07
  • $\begingroup$ @Saaqib, there are proofs in nearly every introductory number theory textbook ever published, and probably on a thousand websites. Why should we duplicate all that effort here? Just go to a library, or type "primitive root" into Google. $\endgroup$ – Gerry Myerson Apr 2 '14 at 12:24

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.