We now consider the problem of finding generators for ${\mathbb{Z}}_n^{*}$ for any $n$. Previously, we only studied generators for prime $n$. To generalize, we follow the most obvious strategy: first consider prime powers, then use the Chinese Remainder Theorem to generalize.

First we see that $1$ is a generator for ${\mathbb{Z}}_2^{*}$ and $3$ is a generator for ${\mathbb{Z}}_4^{*}$. A quick check reveals ${\mathbb{Z}}_8^{*}$ has no generator: the square of any odd number is 1 modulo 8.

Next suppose ${\mathbb{Z}}_{2^k}^{*}$ has a generator $g$ for some $k>3$. Then for each $a\in {\mathbb{Z}}_8^{*}$, we have $g^x=a(mod{2}^k)$ for some $x$. This equation still holds modulo 8 since $8\mid 2^k$. But this is a contradiction since it would imply $g$ is a generator of ${\mathbb{Z}}_8^{*}$.

Thus if $n$ is a power of 2, ${\mathbb{Z}}_n^{*}$ has a generator if and only if $n=2$ or $n=4$.

We can examine the behaviour of units under exponentiation modulo a power of two more closely. By induction we can show that

(first explicitly compute for $t=\mathrm{4,5}$ before proving the inductive step).

From here we can show easily that if $a=\pm 3(mod8)$ then the order of $a$ is $2^{t-2}$ modulo $2^t$, otherwise the order is strictly smaller.

Let $p$ be an odd prime. Let $g$ be a generator of ${\mathbb{Z}}_p^{*}$. We try to find a generator of ${\mathbb{Z}}_{p^2}$.

Intuitively, such a generator ought to somehow depend on the generator for ${\mathbb{Z}}_p^{*}$. So we consider the problem of finding the order of $g+kp$ in ${\mathbb{Z}}_{p^2}$ for any $k$.

Let $t$ be the order of $g+kp$ in ${\mathbb{Z}}_{p^2}^{*}$. Then we also have $(g+kp{)}^t=g^t=1(modp)$, thus $(p-1)\mid t$. Since $t\mid \varphi (p^2)=p(p-1)$, there are two possibilities. Either $t=p-1$ or $t=p(p-1)$. In the latter case, $g+kp$ generates ${\mathbb{Z}}_p^2$.

But the former case, $(g+kp{)}^{p-1}=1(mod{p}^2)$ occurs if and only if

Considering the binomial expansion,

Note $p$ is not invertible, so we go back to first principles and find

(the division is an integer division). In other words, $g+kp$ is a generator of ${\mathbb{Z}}_{p^2}^{*}$ except for one value of $k$. Thus each of the $\varphi (p-1)$ generators of ${\mathbb{Z}}_p^{*}$ can be used to construct $p-1$ generators of ${\mathbb{Z}}_{p^2}^{*}$.

Alternative proof: we show that at least one of $g$ or $g+p$ is a generator:

Consider the binomial expansion gives

Since this is nonzero, we see that $g+p$ and $g$ cannot both be roots of the polynomial $x^{p-1}-1$, hence (at least) one of them has order $p(p-1)$.

Let $g$ be a generator of ${\mathbb{Z}}_{p^2}^{*}$. By considering the binomial expansion and inducting on $r$, we find that if

then

Then the order of $g$ in ${\mathbb{Z}}_{p^{2+r}}^{*}$ must be $\varphi (p^{2+r})$, hence $g$ generates ${\mathbb{Z}}_{p^2+r}^{*}$.

We first consider odd $n$. Write $n=p_1^{k_1}...p_m^{k_m}$. By the Chinese Remainder Theorem we have

Each $x\in {\mathbb{Z}}_n^{*}$ corresponds to some element $(x_1,...,x_n)$ of the right-hand side. Now each $x_i$ satisfies

so if we take the lowest common multiple of the orders

we find $(x_1,...,x_n{)}^{\lambda }=(\mathrm{1,...,1})$, thus $x$ has order dividing $\lambda (n)$. On the other hand, if we choose each $g_i$ to be a generator of ${\mathbb{Z}}_{p_i^{k_i}}$ then $(g_1,...,g_n)$ has order $\lambda (n)$.

Hence a generator exists in ${\mathbb{Z}}_n^{*}$ if and only if $\lambda (n)=\varphi (n)$. Now $\varphi (p_i{)}^{k_i}$ is even thus for $\lambda (n)=\varphi (n)$ implies at most one of the $p_i$ is odd hence $n$ is in fact a prime power.

Now suppose $n=2^{k}q$ where $q$ is odd. Again by the Chinese Remainder Theorem we have ${\mathbb{Z}}_n^{*}={\mathbb{Z}}_{2^k}^{*}\times {\mathbb{Z}}_q^{*}$. If $k>2$ then ${\mathbb{Z}}_n^{*}$ has no generator since ${\mathbb{Z}}_8^{*}$ doesn’t. If $k=2$, since ${\mathbb{Z}}_4^{*}$ has order 2, the lowest common multiple of $\varphi (4)$ and $\varphi (q)$ is less than $\varphi (4q)$, thus no generator exists. Lastly if $k=1$ then if $g$ is a generator for ${\mathbb{Z}}_q$ then $\lambda (n)=\varphi (n)$ thus a generator exists [$(1,g)$ is a generator].

In summary, ${\mathbb{Z}}_n^{*}$ has a generator precisely when $n=2,4,p^k,2p^k$ for odd primes $p$ and positive integers $k$.

Note we can tighten Euler’s Theorem in this sense: in general we can find some $\lambda (n)<\varphi (n)$ such that $a^{\lambda (n)}=1$ for all $a\in {\mathbb{Z}}_n^{*}$, and furthermore there exists $a\in {\mathbb{Z}}_n^{*}$ with order $\lambda (n)$.

From the above, we see if $n=2^k{p}_1^{k_1}...p_m^{k_m}$ for odd primes $p_i$, then we can take

for $k\le 2$ and

for $k>2$.