Since \(\mathbb {Z}_p^* = \mathbb {Z}_p \setminus \{ 0\} \) is a group with multiplication, the set \(\{ 1a, 2a, 3a, \dots , (p-1)a\} \) runs again through all nonzero residues,

and hence by dividing by \((p - 1)!\), we get \(a^{p - 1} \equiv 1 \pmod{p}\).

From Fermat’s little theorem, the polynomial \(x^{p-1} - 1 \in \mathbb {Z}_p[x]\) has as roots all nonzero residues. Next we note that

Suppose \(a \equiv b^2 \pmod{p}\) is a quadratic residue. Then by Fermat’s little theorem \(a^{\frac{p-1}{2}} \equiv b^{p-1} \equiv 1 \pmod{p}\). Hence the quadratic residues are precisely the roots of the first factor \(x^{\frac{p-1}{2}} - 1\), and the \(\frac{p-1}{2}\) nonresidues must thus be the roots of the second factor \(x^{\frac{p-1}{2}} + 1\). Comparing this to the definition of the Legendre symbol, we obtain

This obviously holds for the right-hand side of Euler’s criterion.

Suppose \(u_1, \dots , u_s\) are the residues smaller than \(0\), and that \(v_1, \dots , v_{\frac{p-1}{2} - s}\) are those greater than \(0\). If \(-u_i = v_j\), then \(u_i + v_j \equiv 0 \pmod{p}\). Now \(u_i \equiv ka, v_j \equiv \ell a \pmod{p}\) implies \(p \mid (k + \ell ) a\). As \(p\) and \(a\) are relatively prime, \(p\) must divide \(k + \ell \) which is impossible, since \(k + \ell \le p-1\). Thus the numbers \(-u_1, \dots , -u_s\) are between \(1\) and \(\frac{p-1}{2}\), and are all different from the \(v_j\)’s; hence \(\{ -u_1, \dots , -u_s, v_1, \dots , v_{\frac{p-1}{2} - s}\} = \{ 1, 2, \dots , \frac{p-1}{2}\} \). Therefore

which implies

Now remember how we obtained the numbers \(u_i\) and \(v_j\); they are the residues of \(1a, \dots , \frac{p-1}{2}a\). Hence

Cancelling \(\left(\frac{p-1}{2}\right)!\) together with Euler’s criterion gives

and therefore \((\frac{a}{p}) = (-1)^s\), since \(p\) is odd.

The key to our first proof is a counting formula given by Lemma of Gauss. Let \(p\) and \(q\) be odd primes, and consider \((\frac{q}{p})\). Suppose \(iq\) is a multiple of \(q\) that reduces to negative residue \(r_i {\lt} 0\) in the Lemma of Gauss. This means that there is a unique integer \(j\) such that \(-\frac{p}{2} {\lt} iq-jp {\lt} 0\). Note that \(0 {\lt} j {\lt} \frac{q}{2}\) since \(0 {\lt} i {\lt} \frac{p}{2}\). In other words, \((\frac{q}{p}) = (-1)^s\), where \(s\) is the number of lattice points \((x, y)\), that is, pairs of integers \(x\), \(y\) satisfying

Similarly, \((\frac{p}{q}) = (-1)^t\) where \(t\) is the number of lattice points \((x, y)\) with

Now look at the rectangle with side lengths \(\frac{p}{2}\), \(\frac{q}{2}\), and draw the two lines parallel to the diagonal \(py = qx\), \(y = \frac{q}{p}x + \frac{1}{2}\) or \(py - qx = \frac{p}{2}\), respectively, \(y = \frac{q}{p} \left(x - \frac{1}{2}\right)\) or \(qx - py = \frac{q}{2}\).

The proof is now quickly completed by the following three observations:

1. There are no lattice points on the diagonal and the two parallels. This is so because \(py = qx\) would imply \(p \mid x\), which cannot be. For the parallels observe that \(py - qx\) is an integer while \(\frac{p}{2}\) and \(\frac{q}{2}\) are not.

2. The lattice points observing 2 are precisely the points in the upper strip \(0 {\lt} py - qx {\lt} \frac{p}{2}\), and those of 3 the points in the lower strip \(0 {\lt} qx - py {\lt} \frac{q}{2}\). Hence the number of lattice points in the two strips is \(s + t\).

3. The outer regions \(R : py - qx {\gt} \frac{p}{2}\) and \(S: qx - py {\gt} \frac{q}{2}\) contain the same number of points. To see this consider the map \(\varphi : R \to S\) which maps \((x, y)\) to \(\left(\frac{p+1}{2} - x, \frac{q+1}{2} - y\right)\) and check that \(\varphi \) is an involution.

Since the total number of lattice points in the rectangle is \(\frac{p-1}{2} \cdot \frac{q-1}{2}\), we infer that \(s + t\) and \(\frac{p-1}{2} \cdot \frac{q-1}{2}\) have the same parity, and so

Let \(F^*\) be the multiplicative group of the field \(F\), with \(|F^*| = n\). Writing \(\operatorname{ord}(a)\) for the order of an element, that is, the smallest positive integer \(k\) such that \(a^k = 1\), we want to find an element \(a \in F^*\) with \(\operatorname{ord}(a) = n\). If \(\operatorname{ord}(b) = d\), then by Lagrange’s theorem, \(d\) divides \(n\). Classifying the elements according to their order, we have

If \(\operatorname{ord}(b) = d\), then every element \(b^i\) (\(i = 1, \dots , d\)) satisfies \((b^i)^d = 1\) and is therefore a root of the polynomial \(x^d - 1\). But, since \(F\) is a field, \(x^d - 1\) has at most \(d\) roots, and so the elements \(b, b^2, \dots , b^d = 1\) are precisely these roots. In particular, every element of order \(d\) is of the form \(b^i\).

On the other hand, it is easily checked that \(\operatorname{ord}(b^i) = \frac{d}{(i, d)}\), where \((i, d)\) denotes the greatest common divisor of \(i\) and \(d\). Hence \(\operatorname{ord}(b^i) = d\) if and only if \((i, d) = 1\), that is, if \(i\) and \(d\) are relatively prime. Denoting Euler’s function by \(\varphi (d) = \# \{ i : 1 \le i \le d, (i, d) = 1\} \), we thus have \(\psi (d) = \varphi (d)\) whenever \(\psi (d) {\gt} 0\). Looking at ?? we find

But as we are going to show that

we must have \(\psi (d) = \varphi (d)\) for all \(d\). In particular, \(\psi (n) = \varphi (n) \ge 1\), and so there is an element of order \(n\).

The following (folklore) proof of ?? belongs in the Book as well. Consider the \(n\) fractions

reduce them to the lowest term \(\frac{k}{n} = \frac{i}{d}\) with \(1 \le i \le d\), \((i, d) = 1\), \(d \mid n\), and check that the denominator \(d\) appears precisely \(\varphi (d)\) times.

The prime field of \(F\) is \(\mathbb {Z}_q\), whence \(qa = 0\) for any \(a \in F\). This implies that \((a + b)^q = a^q + b^q\), since any binomial coefficient \(\binom {q}{i}\) is a multiple of \(q\) for \(0 {\lt} i {\lt} q\), and thus 0 in \(F\).

The multiplicative group \(F^* = F \setminus \{ 0\} \) is cyclic of size \(q^{p-1} - 1\). Since by Fermat’s little theorem \(p\) is a divisor of \(q^{p-1} - 1\), there exists an element \(\zeta \in F\) of order \(p\), that is, \(\zeta ^p = 1\), and \(\zeta \) generates the subgroup \(\{ \zeta , \zeta ^2, \dots , \zeta ^p = 1\} \) of \(F^*\). Note that any \(\zeta ^i\) (\(i \ne p\)) is again a generator. Hence we obtain the polynomial decomposition \(x^p - 1 = (x - \zeta ) (x - \zeta ^2) \cdots (x - \zeta ^p)\).

The second proof does not use Gauss’ lemma, instead it employs so-called “Gauss sums” in finite fields. Gauss invented them in his study of the equation \(x^p - 1 = 0\) and the arithmetical properties of the field \(\mathbb {Q}(\zeta )\) (called cyclotomic field), where \(\zeta \) is a \(p\)-th root of unity. They have been the starting point for the search for higher reciprocity laws in general number fields.

Consider the Gauss sum

where \((\frac{i}{p})\) is the Legendre symbol. For the proof we derive two different expressions for \(G^q\) and then set them equal.

First expression. We have

where the first equality follows from \((a + b)^q = a^q + b^q\), the second uses that \((\frac{i}{p})^q = (\frac{i}{p})\) since \(q\) is odd, the third one is derived from ??, which yields \((\frac{i}{p}) = (\frac{q}{p}) (\frac{iq}{p})\), and the last one holds since \(iq\) runs with \(i\) through all nonzero residues modulo \(p\).

Second expression. Suppose we can prove

then we are quickly done. Indeed,

Equating the expressions in 6 and 8 and cancelling \(G\), which is nonzero by ??, we find \((\frac{q}{p}) = (\frac{p}{q}) (-1)^{\frac{p-1}{2} \frac{q-1}{2}}\), and thus

It remains to verify ??, and for this we first make two simple observations:

• \(\sum _{i=1}^{p} \zeta ^i = 0\) and thus \(\sum _{i=1}^{p-1} \zeta ^i = -1\). Just note that \(-\sum _{i=1}^{p} \zeta ^i\) is the coefficient of \(x^{p-1}\) in \(x^p - 1 = \prod _{i=1}^{p} (x - \zeta ^i)\), and thus 0.

• \(\sum _{k=1}^{p-1} (\frac{k}{p}) = 0\) and thus \(\sum _{k=1}^{p-2} (\frac{k}{p}) = - (\frac{-1}{p})\), since there are equally many quadratic residues and nonresidues.

We have

Setting \(j \equiv ik \pmod{p}\) we find

For \(k = p - 1 \equiv -1 \pmod{p}\) this gives \((\frac{-1}{p}) (p - 1)\), since \(\zeta ^{1+k} = 1\). Move \(k = p - 1\) in front and write

Since \(\zeta ^{1+k}\) is a generator of the group for \(k \ne p - 1\), the inner sum equals \(\sum _{i=1}^{p-1} \zeta ^i = -1\) for all \(k \ne p - 1\) by our first observation. Hence the second summand is \(-\sum _{k=1}^{p-2} (\frac{k}{p}) = (\frac{-1}{p})\) by our second observation. It follows that \(G^2 = (\frac{-1}{p}) p\) and thus with Euler’s criterion \(G^2 = (-1)^{\frac{p-1}{2}} p\), which completes the proof.