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 💡