# Which elements of this cyclic group would generate it?

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?

• Exactly when $\;n=1\,,\,n=2\,,\,n=2p\,,\,p^k\;$ , with $\;p\;$ an odd prime. – DonAntonio Apr 2 '14 at 11:05
• This would have been better if you include "I think" with "which, when" rather with only "which,when"... – user87543 Apr 2 '14 at 11:06
• This is explained in almost all books on number theory. – lhf Apr 2 '14 at 11:06
• Ihf, I'd appreciate if you could also give an exact reference where both parts of my question are answered. – Saaqib Mahmood Apr 2 '14 at 12:04
• 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. – Gerry Myerson Apr 2 '14 at 12:26

## 1 Answer

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.

• Instead of gcd, you mean lcm, I think. – Saaqib Mahmood Apr 2 '14 at 11:58
• But $U_{18}$ IS cyclic although $18 = 2 \times 9$ and gcd($2, \ , 9$) $=1$. – Saaqib Mahmood Apr 2 '14 at 12:00
• @SaaqibMahmuud, thanks for the correction. In the example you gave, $\phi(2)$ is not even. – lhf Apr 2 '14 at 12:01
• Ihf, can you please write out a complete proof for me? I'm rather rusty on even the elementary number theory! – Saaqib Mahmood Apr 2 '14 at 12:07
• @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. – Gerry Myerson Apr 2 '14 at 12:24