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:

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

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

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

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

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.

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