Is there an easy way to tell, for a given $n$, which elements in $\mathbb{Z}^\times_n$ are its generators?
This came up when I was doing a homework problem for my Abstract Algebra course. The problem was, "Determine all $n$ such that $\mathbb{Z}^\times_{n}$ is cyclic. List all the orders of all the elements for each of $\mathbb{Z}^\times_3 \dots \mathbb{Z}^\times_{12}$. For $n$ such that $\mathbb{Z}^\times_n$ is cyclic, list its generators."
I did the problem by brute force, but is there a closed formula? (I'm happy with considering only $n$ such that $\mathbb{Z}^\times_n$ is cyclic).
Obviously $1$ is never a generator. $n - 1$ is congruent to $-1$ mod $n$, so neither is it a generator.
Can we completely characterize the generators of $\mathbb{Z}^\times_n$ (when it's cyclic?)