Generators: The General Case

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.

Powers of Two

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 \gt 3$. Then for each $a \in \mathbb{Z}_8^*$, we have $g^x = a \pmod{2^k}$ for some $x$. This equation still holds modulo 8 since $8 | 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

$(1+2n)^{2^{t-3}} = 1 + 2^{t-2}(n - n^2 + 2n^4)$

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

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

Squares of Odd Primes

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 + k p$ in $\mathbb{Z}_{p^2}$ for any $k$.

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

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

$(g + k p)^p = g + k p \pmod{p^2} .$

Considering the binomial expansion,

$g^p - g = k p \pmod{p^2} .$

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

$k = (g^p - g)/p \pmod {p}$

(the division is an integer division). In other words, $g + k p$ is a generator of $\mathbb{Z}_{p^2}^*$ except for one value of $k$. Thus each of the $\phi(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:

$\array { ((g+p)^{p-1} - 1) - (g^{p-1} - 1) &=& (g+p)^{p-1} - g^{p-1} \\ &=& (g+p-g)((g+p)^{p-2} + (g+p)^{p-3}g + ... + g^{p-2}) }$

Consider the binomial expansion gives

$((g+p)^{p-1} - 1) - (g^{p-1} - 1) = p((p-1)g^{p-2} + p(...)) = -p g^{p-2}$

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)$.

Powers of Odd Primes

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

$g^t = 1 + k p^s \pmod{p^{s+1}}$

then

$g^{t p^r} = 1 + k p^{s+r} \pmod{p^{s+r+1}} .$

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

The General Case

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

$\mathbb{Z}_n^* = \mathbb{Z}_{p_1^{k_1}}^* \times ... \times \mathbb{Z}_{p_m^{k_m}}^*$

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

$x_i^{\phi(p_i^{k_i})} = 1 \pmod{p_i^{k_i}}$

so if we take the lowest common multiple of the orders

$\lambda(n) = \mathrm{lcm}(\phi(p_1^{k_1}),...,\phi(p_m^{k_m}))$

we find $(x_1,...,x_n)^\lambda = (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) = \phi(n)$. Now $\phi(p_i)^{k_i}$ is even thus for $\lambda(n) = \phi(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 \gt 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 $\phi(4)$ and $\phi(q)$ is less than $\phi(4q)$, thus no generator exists. Lastly if $k = 1$ then if $g$ is a generator for $\mathbb{Z}_q$ then $\lambda(n) = \phi(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) \lt \phi(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

$\lambda(n) = \mathrm{lcm}(\phi(2^k), \phi(p_1^{k_1}) ,..., \phi(p_m^{k_m}))$

for $k \le 2$ and

$\lambda(n) = \mathrm{lcm}(\phi(2^{k-1}), \phi(p_1^{k_1}) ,..., \phi(p_m^{k_m}))$

for $k \gt 2$.