# Generators: The General Case

We previously studied generators of $$\mathbb{Z}_n^*$$ for prime $$n$$. How do we generalize to any $$n$$?

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 > 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 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) \pmod{2^t}$

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

From here one can show 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 relate to the generators of $$\mathbb{Z}_p^*$$. So 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}^*$$. From $$(g+k p)^t = g^t = 1 \pmod{p}$$ we deduce $$(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} .$

As $$p$$ is not invertible, 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:

\begin{aligned} ((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}) \\ &= p((p-1)g^{p-2} + p(...)) \end{aligned}

by considering the binomial expansion. Thus:

$((g+p)^{p-1} - 1) - (g^{p-1} - 1) = p(p-1) g^{p-2} = -p g^{p-2} \pmod {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}^*$$. We show $$g$$ is a generator for all powers of $$p$$.

First, a lemma. Suppose for some $$s \ge 1$$:

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

Then for any $$r \ge 0$$, by considering the binomial expansion and inducting on $$r$$, we have:

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

We use this lemma to show $$g$$ also generates $$\mathbb{Z}_p^*$$ (which implies the generators we constructed above are the only generators of $$\mathbb{Z}_{p^2}^*$$, though we could also show this via a counting argument). If $$g$$ has order $$t$$ modulo $$p$$, then:

$g^t = 1 + k p$

for some $$k$$, and setting $$s = 1, r = 1$$ in the lemma yields:

$g^{t p} = 1 \pmod {p^2}$

Since $$g$$ generates $$\mathbb{Z}_{p^2}^*$$, the exponent $$tp$$ must be a multiple of $$\phi(p^2) = p(p - 1)$$. Therefore $$t$$ is a multiple of $$p - 1 = \phi(p)$$ so $$g$$ generates $$\mathbb{Z}_p^*$$. (We can generalize to show any generator for a prime power is also a generator for any lower power.)

Using the lemma is somewhat gratuitous as we could have reasoned as above when we showed a generator of a power of 2 must be a generator of lower power of 2, but on the other hand it’s satisfying to use one lemma to dispatch all the cases.

Now for the other powers of $$p$$. We just established $$g$$ generates $$\mathbb{Z}_p^*$$, that is:

$g^{p-1} = 1 + k p$

for some $$k$$, which must be coprime to $$p$$ as $$g$$ generates $$\mathbb{Z}_{p^2}^*$$.

Applying the lemma with $$t = p - 1, s = 1$$ gives:

$g^{(p-1)p^r} = 1 + k p^{1+r} \pmod {p^{r+2}}$

When $$r = 1$$, this is:

$g^{\phi(p^2)} = 1 + k p^2 \pmod {p^3}$

Let $$t$$ be the order of $$g$$ modulo $$p^3$$ so $$t | \phi(p^3)$$. We also have:

$g^t = 1 \pmod {p^2}$

which means $$\phi(p^2) | t$$ because $$g$$ generates $$\mathbb{Z}_{p^2}^*$$. Thus $$t$$ is either $$\phi(p^2)$$ or $$\phi(p^3)$$. It cannot be the former since $$k$$ is coprime to $$p$$, thus it must be the latter and thus $$g$$ generates $$\mathbb{Z}_{p^3}^*$$.

We iterate this argument for higher powers of $$p$$.

## 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)$$. Since each $$\phi(p_i^{k_i})$$ is even, $$\lambda(n) = \phi(n)$$ can only when $$m = 1$$, that is, $$n$$ must be 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 $$\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$$.

We can use the above to tighten Euler’s Theorem. Write $$n = 2^k p_1^{k_1}...p_m^{k_m}$$ for odd distinct primes $$p_i$$, and define

$\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 > 2$$.

Then $$a^{\lambda(n)} = 1$$ for all $$a\in\mathbb{Z}_n^*$$, and furthermore $$\lambda(n)$$ is the smallest positive integer satisfying this condition because there exists $$a\in\mathbb{Z}_n^*$$ with order $$\lambda(n)$$.

We can apply our new knowledge to study quadratic residues in more general settings.

If $$\mathbb{Z}_n^*$$ has a generator, then $$\phi(n)$$ plays the same role as $$p - 1$$ in the odd prime case for quadratic residues.

For example, let us consider when $$-1$$ is a quadratic residue.

For odd primes $$p$$, $$\phi(p^k) = p^k - p^{k-1}$$, which is 0 or 2 mod 4 depending on whether $$p$$ is 1 or 3 mod 4, so $$-1$$ is a quadratic residue in $$\mathbb{Z}_p^k$$ if and only if $$p = 1 \pmod {4}$$.

For $$p = 2$$, if $$n$$ is a quadratic residue modulo $$2^k$$ then it must also be a quadratic residue for all lower powers of $$2$$, which implies, for example, $$-1$$ is a quadratic residue only when $$k = 1$$.

Write $$n = \prod 2^k p_i^{k_i}$$ for odd distinct primes $$p_i$$. By the Chinese remainder theorem, $$-1$$ is a quadratic residue if and only if $$k \le 1$$ and each $$p_i = 1 \bmod 4$$.

Ben Lynn blynn@cs.stanford.edu 💡