## A Consequence of Gauss' Lemma

We can use Gauss' Lemma to establish that $\displaystyle{\left(\frac{2}{p}\right) = (-1)^{(p^2-1)/8}}$ for odd primes $p$.

*Proof:*

For an odd prime $p$, one of the following cases must hold: $p \equiv \pm 1\pmod{8}$ or $p \equiv \pm 3\pmod{8}$. We will consider the case where $p \equiv 1\pmod{8}$; the others are handled in a similar manner.

If $p \equiv 1\pmod{8}$, then $p = 8m+1$ for some integer $m$.

Consider the values $2a\pmod{p}$, where $a$ is an odd positive integer less than $p$:
$$2 \cdot 1,\, 2 \cdot 3,\, 2 \cdot 5,\, \ldots,\, 2(4m-1) \, \textrm{ and } \, 2(4m+1),\, 2(4m+3),\, \ldots,\, 2(8m-1)$$
Equivalently,
$$2, 6, 10, \ldots, (8m-2) \, \textrm{ and } \, (8m+2), (8m+6), \ldots, (16m-2)$$
We need to find the least residues associated with each of these. To this end, note that all of the values in the first part of the list are less than $p$, and thus already least residues. However, the values in the second part of the list are between $p$ and $2p$, and thus require the subtraction of a single $p$ each to find the respective least residue $\pmod{p}$.

This gives us least residues of
$$2, 6, 10, \ldots, (8m-2) \, \textrm{ and } \, (8m+2)-p, (8m+6)-p, \ldots, (16m-2)-p$$

The values in the first part of our list clearly even, while the values in the second part of our list - being the difference of an even value and an odd prime - are all odd.

There are $2m$ elements in the first part of our list, thus by Gauss' Lemma,
$$\displaystyle{\left(\frac{2}{p}\right) = (-1)^{2m} = +1}$$

One can easily show that in the cases when $p \equiv \pm 3\pmod{8}$, the number of elements in the first part of our original list (i.e., those values less than $p$) shifts by $1$, while when $p \equiv -1\pmod{8}$, this number of elements remains unchanged. This results in a similar shift in final exponent above.

Putting all of the cases together, we have
$$\left(\frac{2}{p}\right) = \left\{\begin{array}{rcl}
+1 & \textrm{ if } & p \equiv \pm 1\pmod{8}\\
-1 & \textrm{ if } & p \equiv \pm 3\pmod{8}\\
\end{array}\right.$$

We can write this more succinctly if we notice that if $p \equiv \pm 1\pmod{8}$, then $(p^2-1)/8$ must be even, while if $p \equiv \pm 3\pmod{8}$, then $(p^2-1)/8$ must be odd. As such,

$$\left(\frac{2}{p}\right) = (-1)^{(p^2-1)/8} \textrm{ for odd primes } p$$