# 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

(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

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 + 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:

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

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

then

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

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 = (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

for \(k \le 2\) and

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

*blynn@cs.stanford.edu*💡