# 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)$$. Since each $$\phi(p_i)^{k_i}$$ is even, $$\lambda(n) = \phi(n)$$ can only occur if there is only one such term, that is, $$m = 1$$ so $$n$$ is 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$$.

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

## Quadratic Residues

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 💡