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