Closed formula for the generators of $\mathbb{Z}^\times_n$?

Question

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?)

Answer 1

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.

Answer 2

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.