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