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

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.
• 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