[proofplan] We prove the supplementary law by giving the special case of [Gauss's lemma](/theorems/858) needed for $a=2$. For the residues $2,4,\dots,p-1$, we compare their least positive residues with $p/2$ and count how many must be replaced by their negatives to land in the interval $\{1,\dots,(p-1)/2\}$. This count determines the sign of $2^{(p-1)/2}$ modulo $p$, hence the Legendre symbol, and its parity is computed from the residue class of $p$ modulo $8$. [/proofplan] [step:Reduce the Legendre symbol to a signed product of least residues] Let \begin{align*} m:=\frac{p-1}{2}. \end{align*} Since $p$ is odd, $m \in \mathbb{N}$. For each $k \in \{1,\dots,m\}$, define $r_k \in \{1,\dots,p-1\}$ to be the least positive residue of $2k$ modulo $p$. Since $1 \leq k \leq m$, we have $2 \leq 2k \leq p-1$, so in fact \begin{align*} r_k=2k. \end{align*} Define \begin{align*} N:=\#\{k \in \{1,\dots,m\}: r_k>p/2\}. \end{align*} For each $k \in \{1,\dots,m\}$, define $s_k \in \{1,\dots,m\}$ by \begin{align*} s_k= \begin{cases} r_k, & r_k<p/2, \end{align*} \begin{align*} p-r_k, & r_k>p/2. \end{cases} \end{align*} The case $r_k=p/2$ cannot occur because $p$ is odd and $r_k$ is an integer. We claim that the numbers $s_1,\dots,s_m$ are pairwise distinct. If $s_i=s_j$, then from the definition of $s_i$ and $s_j$ we have \begin{align*} 2i \equiv 2j \pmod{p} \end{align*} or \begin{align*} 2i \equiv -2j \pmod{p}. \end{align*} Since $p$ is odd, $2$ is invertible modulo $p$. Hence either $i \equiv j \pmod{p}$ or $i \equiv -j \pmod{p}$. In the first case, $1 \leq i,j \leq m < p$ gives $i=j$. In the second case, $p \mid i+j$, but \begin{align*} 2 \leq i+j \leq 2m=p-1, \end{align*} which is impossible. Thus $i=j$, so the $s_k$ are pairwise distinct. Since there are $m$ of them and all lie in $\{1,\dots,m\}$, they are precisely the elements of $\{1,\dots,m\}$ in some order. Multiplying the congruences $s_k \equiv 2k \pmod{p}$ for $r_k<p/2$ and $s_k \equiv -2k \pmod{p}$ for $r_k>p/2$, we get \begin{align*} \prod_{k=1}^{m}s_k \equiv (-1)^N 2^m \prod_{k=1}^{m}k \pmod{p}. \end{align*} Since $\{s_1,\dots,s_m\}=\{1,\dots,m\}$, the left-hand product is $\prod_{k=1}^{m}k$. None of $1,\dots,m$ is divisible by $p$, so this product is invertible modulo $p$. Cancelling it gives \begin{align*} 2^m \equiv (-1)^N \pmod{p}. \end{align*} By the definition of the Legendre symbol, $\left(\frac{2}{p}\right)=1$ exactly when $2$ is a square modulo $p$, and $\left(\frac{2}{p}\right)=-1$ otherwise. The standard Euler criterion for the Legendre symbol therefore gives \begin{align*} \left(\frac{2}{p}\right)\equiv 2^m \equiv (-1)^N \pmod{p}. \end{align*} Both $\left(\frac{2}{p}\right)$ and $(-1)^N$ belong to $\{-1,1\}$, and because $p$ is odd these two integers are congruent modulo $p$ only if they are equal. Hence \begin{align*} \left(\frac{2}{p}\right)=(-1)^N. \end{align*} [guided] The point of the argument is to measure the sign introduced when the residues $2,4,\dots,2m$ are folded into the lower half of the nonzero residue classes modulo $p$. Let \begin{align*} m:=\frac{p-1}{2}. \end{align*} Because $p$ is odd, $m$ is a positive integer. For each $k \in \{1,\dots,m\}$, let $r_k \in \{1,\dots,p-1\}$ denote the least positive residue of $2k$ modulo $p$. In this special case there is no wraparound: since $2 \leq 2k \leq p-1$, we have \begin{align*} r_k=2k. \end{align*} Now define \begin{align*} N:=\#\{k \in \{1,\dots,m\}: r_k>p/2\}. \end{align*} This is the number of residues $2k$ lying in the upper half of the nonzero residues modulo $p$. For each $k$, define $s_k$ by folding $r_k$ into the lower half: \begin{align*} s_k= \begin{cases} r_k, & r_k<p/2, \end{align*} \begin{align*} p-r_k, & r_k>p/2. \end{cases} \end{align*} The equality $r_k=p/2$ cannot occur, since $p/2$ is not an integer while $r_k$ is. We first verify that $s_1,\dots,s_m$ are exactly the numbers $1,\dots,m$ in some order. Each $s_k$ lies in $\{1,\dots,m\}$ by construction. Suppose $s_i=s_j$. Then the two original residues $2i$ and $2j$ are either congruent or negatives of one another modulo $p$, so \begin{align*} 2i \equiv 2j \pmod{p} \end{align*} or \begin{align*} 2i \equiv -2j \pmod{p}. \end{align*} Since $p$ is odd, $2$ has a multiplicative inverse modulo $p$. Therefore either $i \equiv j \pmod{p}$ or $i \equiv -j \pmod{p}$. The first congruence forces $i=j$ because both $i$ and $j$ lie between $1$ and $m<p$. The second congruence would imply $p \mid i+j$, but \begin{align*} 2 \leq i+j \leq 2m=p-1, \end{align*} so $p$ cannot divide $i+j$. Thus $i=j$, proving pairwise distinctness. Since there are $m$ distinct numbers in the $m$-element set $\{1,\dots,m\}$, they are precisely that set. We now multiply the congruences defining the folding. If $r_k<p/2$, then $s_k=r_k\equiv 2k \pmod{p}$. If $r_k>p/2$, then $s_k=p-r_k\equiv -2k \pmod{p}$. Exactly $N$ indices are of the second type, so \begin{align*} \prod_{k=1}^{m}s_k \equiv (-1)^N 2^m \prod_{k=1}^{m}k \pmod{p}. \end{align*} But the $s_k$ are a permutation of $1,\dots,m$, hence \begin{align*} \prod_{k=1}^{m}s_k=\prod_{k=1}^{m}k. \end{align*} No factor $1,\dots,m$ is divisible by $p$, so the product is invertible modulo $p$ and may be cancelled. We obtain \begin{align*} 2^m \equiv (-1)^N \pmod{p}. \end{align*} [Euler's criterion](/theorems/1715) identifies $2^m$ modulo $p$ with the Legendre symbol $\left(\frac{2}{p}\right)$. Thus \begin{align*} \left(\frac{2}{p}\right)\equiv (-1)^N \pmod{p}. \end{align*} Both sides are ordinary integers equal to $1$ or $-1$. Since $p$ is odd, two such integers congruent modulo $p$ must be equal. Therefore \begin{align*} \left(\frac{2}{p}\right)=(-1)^N. \end{align*} [/guided] [/step] [step:Count the residues in the upper half] Since $r_k=2k$, the condition $r_k>p/2$ is equivalent to \begin{align*} k>\frac{p}{4}. \end{align*} Thus \begin{align*} N=\#\{k \in \{1,\dots,m\}: k>p/4\}. \end{align*} The integers counted are \begin{align*} \lfloor p/4\rfloor+1,\dots,m, \end{align*} so \begin{align*} N=m-\lfloor p/4\rfloor. \end{align*} Writing $p=4q+1$ or $p=4q+3$, this gives \begin{align*} N= \begin{cases} q, & p=4q+1, \end{align*} \begin{align*} q+1, & p=4q+3. \end{cases} \end{align*} Equivalently, \begin{align*} N=\left\lfloor\frac{p+1}{4}\right\rfloor. \end{align*} [/step] [step:Compare the parity of the count with $(p^2-1)/8$] Since $p$ is odd, write $p=2a+1$ for some integer $a \geq 1$. Then \begin{align*} \frac{p^2-1}{8}=\frac{(p-1)(p+1)}{8}=\frac{a(a+1)}{2}, \end{align*} so $(p^2-1)/8$ is an integer. We compare parities modulo $8$. If $p=8q+1$, then \begin{align*} N=\left\lfloor\frac{8q+2}{4}\right\rfloor=2q \end{align*} and \begin{align*} \frac{p^2-1}{8}=\frac{(8q+1)^2-1}{8}=8q^2+2q, \end{align*} so both are even. If $p=8q+3$, then \begin{align*} N=\left\lfloor\frac{8q+4}{4}\right\rfloor=2q+1 \end{align*} and \begin{align*} \frac{p^2-1}{8}=\frac{(8q+3)^2-1}{8}=8q^2+6q+1, \end{align*} so both are odd. If $p=8q+5$, then \begin{align*} N=\left\lfloor\frac{8q+6}{4}\right\rfloor=2q+1 \end{align*} and \begin{align*} \frac{p^2-1}{8}=\frac{(8q+5)^2-1}{8}=8q^2+10q+3, \end{align*} so both are odd. If $p=8q+7$, then \begin{align*} N=\left\lfloor\frac{8q+8}{4}\right\rfloor=2q+2 \end{align*} and \begin{align*} \frac{p^2-1}{8}=\frac{(8q+7)^2-1}{8}=8q^2+14q+6, \end{align*} so both are even. Therefore \begin{align*} (-1)^N=(-1)^{(p^2-1)/8}. \end{align*} Combining this with the previous step gives \begin{align*} \left(\frac{2}{p}\right)=(-1)^{(p^2-1)/8}. \end{align*} [/step] [step:Extract the quadratic residue criterion modulo $8$] By the definition of the Legendre symbol for an odd prime $p$, the integer $2$ is a [quadratic residue](/page/Quadratic%20Residue) modulo $p$ if and only if \begin{align*} \left(\frac{2}{p}\right)=1. \end{align*} From the formula just proved, this occurs if and only if $(p^2-1)/8$ is even. The parity computation above shows that this happens precisely for \begin{align*} p \equiv 1 \pmod{8} \end{align*} or \begin{align*} p \equiv 7 \pmod{8}. \end{align*} This proves both the stated formula and the equivalent congruence criterion. [/step]