Generators: The General Case

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

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

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

Considering the binomial expansion,

As \(p\) is not invertible, 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:

by considering the binomial expansion. Thus:

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

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

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

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:

for some \(k\), and setting \(s = 1, r = 1\) in the lemma yields:

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:

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:

When \(r = 1\), this is:

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

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

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

for \(k \le 2\) and

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