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

**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

**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$. 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.

**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}$).