Closed formula for the generators of $\mathbb{Z}^\times_n$? 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?)
 A: The generators of $\mathbb{Z}^\times_n$ are exactly $g^k$ where $g$ is one fixed generator and $\gcd(k,\phi(n))=1$.
Thus, there are exactly $\phi(\phi(n))$ generators. All this comes from the theory of cyclic groups.
The hard part is finding one generator, aka a primitive root. No easy way or closed formula is known for that, but the least primitive root is frequently quite small.
A: Here is a way to find a generator — not a closed form. 
Note first that by the Chinese Remainder theorem, it comes down to finding a generator  for $(\mathbf Z/p^r\mathbf Z)^\times$, $p$ a  prime.
The group $(\mathbf Z/p\mathbf Z)^\times$ is cyclic. Let $a$ such that $a\bmod p$ is a generator of this group. Then the order of $a\bmod p^r$ is a multiple of $p-1$, and some power of $s$, say $b$, has order $p-1$.
On the other hand, one shows by induction on $k$ that
$$(1+p)^{p^k}=1+\alpha p^{k+1}, \quad\gcd(\alpha,p)=1$$
There results  that $1+p$ has order $p^{r-1}$. As $\gcd(p-1,p^{r-1})=1$, we know $b(1+p)$ has order $(p-1)p^{r-1}=\varphi(p^r)$. This means $b(1+p)$ is a generator.
Note: One shows $\mathbf Z/n\mathbf Z$ is cyclic if and only if


*

*$n=2$ or $4$,

*$n=p^r$, $p$ being an odd prime,

*or $n=2p^r$, $p$ an odd prime.

