Gauss' Lemma

There is a less obvious way to compute the Legendre symbol. Among other things, we can use it to easily find \(\left(\frac{2}{p}\right)\). Before stating the method formally, we demonstrate it with an example.

Let \(p = 17\), and \(a = 7\). There are \(16\) nonzero elements \([1..16]\). Consider the first half \([1..8]\) and multiply them all by 7 to get 7, 14, 4, 11, 1, 8, 15, 5. We’ve singled out 14, 11 and 15 because they are greater than \(p / 2\) (that is, \(9\) or higher).

So exactly \(3\) of them are greater than \(p/2\). Gauss' Lemma states that if we take this \(3\) and raise \(-1\) to this power, then we have \(\left(\frac{a}{p}\right)\), that is:

\[ \left(\frac{7}{17}\right) = (-1)^3 = -1. \]

Theorem (Gauss' Lemma): Let \(p\) be an odd prime, \(q\) be an integer coprime to \(p\). Take the least residues of \(\{q, 2q, ..., q(p-1)/2\}\), that is, reduce them to integers in \([0..p-1]\). Let \(u\) be the number of members in this set that are greater than \(p/2\). Then

\[ \left(\frac{q}{p}\right) = (-1)^u . \]

Proof: Let \(b_1,...,b_t\) be the members of the set less than \(p/2\), and \(c_1,...,c_u\) be the members greater than \(p/2\). Then \(u + t = (p-1)/2\). Consider the sequence

\[ 0 < b_1,...,b_t,p-c_1, ...,p-c_u < p/2 \]

Each of these are distinct: clearly \(b_i \ne b_j\) and \(c_i \ne c_j\) whenever \(i \ne j\) (since \(q\) is invertible), and if \(b_i = p - c_j\), then let \(b_i = r q, c_j = s q\). Then \(r + s = 0\), which is a contradiction since

\[ 0 < r,s < p / 2 . \]

Hence they must be precisely the numbers \(1,...,(p-1)/2\) in some order, thus

\[ \begin{aligned} q(2q)...(q(p-1)/2) &=& b_1...b_t c_1...c_u \\ &=& (-1)^u b_1...b_t (p - c_1)...(p - c_u) \\ &=& (-1)^u \left(\frac{p-1}{2}\right)! \end{aligned} \]

Dividing both sides by \(((p-1)/2))!\) completes the proof.∎

For example, let \(p\) be an odd prime and take \(q = 2\). The sequence \(2, 2 \times 2,...,2(p-1)/2\) consists of positive least residues. We have \(p = 8 x + y\) for some integer \(x\) and \(y \in \{1,3,5,7\}\). By considering each case we see that the number of elements greater than \(p/2\) is even when \(p = 1, 7 \pmod{8}\) and odd when \(p = 3, 5 \pmod{8}\). We restate this as follows.

Theorem: Let \(p\) be an odd prime.

\[ \left(\frac{2}{p}\right) = (-1)^{\frac{p^2 - 1}{8}} = (-1)^{\lfloor \frac{p+1}{4} \rfloor} \]

Proof: See the last paragraph, and note that \((p^2 - 1) / 8\) is even when \(p = \pm 1 \pmod{8}\) and odd otherwise. Similarly for \( \lfloor (p+1)/4 \rfloor \).∎

Example: By Gauss' Lemma, \(\left(\frac{3}{p}\right) = 1\) if \(p = \pm 1 \pmod{12}\) and \(-1\) otherwise (that is, \(p = \pm 5 \pmod{12}\)). Combining this with the above result for \(-1 \pmod {p}\) we have \(\left(\frac{-3}{p}\right) = 1\) if \(p = 1 \pmod{6}\) and \(-1\) otherwise (\(p = -1 \pmod{6}\)).


Ben Lynn blynn@cs.stanford.edu 💡