## Gauss' Lemma

There is a less obvious way to compute the Legendre symbol. This method allows us to easily evaluate $\left(\frac{2}{p}\right)$, among other things. 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$. Consider the set $\{q, 2q, ..., q(p-1)/2\}$ and view each member is an integer 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 \lt b_1,...,b_t,p-c_1, ...,p-c_u \lt 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 \lt r,s \lt p / 2 .$

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

$\array { 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)! }$

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

For example, let $p$ be an odd prime and take $q = 2$. Consider the sequence $2, 2 \times 2,...,2(p-1)/2$. Note these are positive least residues. Now $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 can 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}$).