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

• This page deals with a specific case, but may be of some use anyway.
– Mark
Feb 29, 2016 at 0:23
• once you found one $g$, the others are $g^a$ where $gcd(a,\phi(n)) = 1$, Feb 29, 2016 at 1:00

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.

• No closed formula! I wonder how difficult it can get to find a primitive root -- which I suppose is the same as asking how large a primitive root can be. Is any bound known? Feb 29, 2016 at 4:02
• @EliRose, for bounds, see en.wikipedia.org/wiki/….
– lhf
Feb 29, 2016 at 11:06

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.
• I don't get what is $b$ : it is an element of $\mathbb{Z}_{p^{k-1}}^\times$ ? Feb 29, 2016 at 1:05
• Yes, and it is a power of the cyclic subgroup generated by $a$. Feb 29, 2016 at 1:26