Which elements of this cyclic group would generate it?

Question

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?

Answer 1

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.