[proofplan] Apply [Gauss's Lemma](/theorems/1719) with $a = 2$: for each $j \in \{1, \ldots, (p-1)/2\}$, the product $2j$ lies in $\{2, 4, \ldots, p-1\}$ already, so no reduction modulo $p$ is needed — we only have to count how many $j$ have $2j > (p-1)/2$. A direct count in terms of $p$ gives $\mu = (p-1)/2 - \lfloor (p-1)/4 \rfloor$, and then a case analysis over $p \bmod 8$ shows the parity of $\mu$ coincides with the parity of $(p^2 - 1)/8$. This yields the closed form $\left(\frac{2}{p}\right) = (-1)^{(p^2-1)/8}$. [/proofplan] [step:Set up Gauss's Lemma with $a = 2$] Let $p$ be an odd prime. Then $(2, p) = 1$, so [Gauss's Lemma](/theorems/1719) applies: \begin{align*} \left(\frac{2}{p}\right) = (-1)^\mu, \qquad \mu = \#\left\{ j \in \left\{1, \ldots, \tfrac{p-1}{2}\right\} : 2j \bmod p \in \left\{\tfrac{p+1}{2}, \ldots, p-1\right\}\right\}. \end{align*} For $j \in \{1, \ldots, (p-1)/2\}$, $2j \in \{2, 4, \ldots, p-1\}$, so $2j$ is already in the range $\{1, \ldots, p-1\}$ and no reduction is needed: $2j \bmod p = 2j$. Hence \begin{align*} \mu = \#\left\{ j \in \left\{1, \ldots, \tfrac{p-1}{2}\right\} : 2j > \tfrac{p-1}{2}\right\} = \#\left\{j : j > \tfrac{p-1}{4}\right\}. \end{align*} [/step] [step:Count $\mu$ as an explicit function of $p$] Let $M = (p-1)/2$. Then \begin{align*} \mu = \#\{j \in \{1, \ldots, M\} : j > (p-1)/4\} = M - \#\{j \in \{1, \ldots, M\} : j \le (p-1)/4\}. \end{align*} Since $p$ is odd, write $p - 1 = 2M$. The integers $j \in \{1, \ldots, M\}$ with $j \le (p-1)/4$ are exactly those with $j \le \lfloor (p-1)/4 \rfloor$, and since $\lfloor (p-1)/4 \rfloor \le M$, this count equals $\lfloor (p-1)/4 \rfloor$. Therefore \begin{align*} \mu = \frac{p-1}{2} - \left\lfloor \frac{p-1}{4} \right\rfloor. \end{align*} [/step] [step:Compute $\mu \bmod 2$ by case analysis over $p \bmod 8$] Since $p$ is odd, $p$ lies in one of four residue classes modulo $8$: $p \in \{1, 3, 5, 7\} \pmod 8$. We compute $\mu$ modulo $2$ in each case by writing $p = 8k + r$ with $r \in \{1, 3, 5, 7\}$ and evaluating. **Case $p \equiv 1 \pmod 8$, so $p = 8k + 1$:** \begin{align*} \frac{p-1}{2} = 4k, \qquad \left\lfloor \frac{p-1}{4} \right\rfloor = \left\lfloor 2k \right\rfloor = 2k, \qquad \mu = 4k - 2k = 2k. \end{align*} So $\mu$ is even. **Case $p \equiv 3 \pmod 8$, so $p = 8k + 3$:** \begin{align*} \frac{p-1}{2} = 4k + 1, \qquad \left\lfloor \frac{p-1}{4} \right\rfloor = \left\lfloor 2k + \tfrac{1}{2} \right\rfloor = 2k, \qquad \mu = 4k + 1 - 2k = 2k + 1. \end{align*} So $\mu$ is odd. **Case $p \equiv 5 \pmod 8$, so $p = 8k + 5$:** \begin{align*} \frac{p-1}{2} = 4k + 2, \qquad \left\lfloor \frac{p-1}{4} \right\rfloor = \left\lfloor 2k + 1 \right\rfloor = 2k + 1, \qquad \mu = 4k + 2 - (2k + 1) = 2k + 1. \end{align*} So $\mu$ is odd. **Case $p \equiv 7 \pmod 8$, so $p = 8k + 7$:** \begin{align*} \frac{p-1}{2} = 4k + 3, \qquad \left\lfloor \frac{p-1}{4} \right\rfloor = \left\lfloor 2k + \tfrac{3}{2} \right\rfloor = 2k + 1, \qquad \mu = 4k + 3 - (2k + 1) = 2k + 2. \end{align*} So $\mu$ is even. In summary, $\mu$ is even when $p \equiv \pm 1 \pmod 8$ and odd when $p \equiv \pm 3 \pmod 8$. [/step] [step:Identify the parity of $\mu$ with $(p^2 - 1)/8$] We also compute the integer $(p^2 - 1)/8$ and its parity in each case. Since $p$ is odd, $p^2 \equiv 1 \pmod 8$, so $(p^2 - 1)/8$ is a nonnegative integer. **Case $p = 8k + 1$:** $p^2 - 1 = 64k^2 + 16k = 16 k(4k + 1)$, so $(p^2 - 1)/8 = 2k(4k + 1)$, which is even. **Case $p = 8k + 3$:** $p^2 - 1 = 64k^2 + 48k + 8 = 8(8k^2 + 6k + 1)$, so $(p^2 - 1)/8 = 8k^2 + 6k + 1$, which is odd. **Case $p = 8k + 5$:** $p^2 - 1 = 64k^2 + 80k + 24 = 8(8k^2 + 10k + 3)$, so $(p^2 - 1)/8 = 8k^2 + 10k + 3$, which is odd. **Case $p = 8k + 7$:** $p^2 - 1 = 64k^2 + 112k + 48 = 8(8k^2 + 14k + 6)$, so $(p^2 - 1)/8 = 8k^2 + 14k + 6$, which is even. Comparing with the previous step, \begin{align*} \mu \equiv \frac{p^2 - 1}{8} \pmod{2}. \end{align*} [/step] [step:Combine Gauss's Lemma with the parity identity] From the previous steps, \begin{align*} \left(\frac{2}{p}\right) = (-1)^\mu = (-1)^{(p^2-1)/8}. \end{align*} Reading off the four cases, this equals $+1$ when $p \equiv \pm 1 \pmod 8$ and $-1$ when $p \equiv \pm 3 \pmod 8$. [guided] Let us recap the structure. [Gauss's Lemma](/theorems/1719) says $\left(\frac{a}{p}\right) = (-1)^\mu$ with $\mu$ counting how many of $a, 2a, \ldots, \frac{p-1}{2} a$ reduce into the "upper half" $\{(p+1)/2, \ldots, p-1\}$ modulo $p$. When $a = 2$, the multiples $2, 4, \ldots, p-1$ are already positive integers less than $p$, so no modular reduction is needed — they just are, as integers, in the range $\{1, \ldots, p-1\}$. The count $\mu$ is therefore the (genuinely elementary) count of how many $j \in \{1, \ldots, (p-1)/2\}$ satisfy $2j > (p-1)/2$, i.e. $j > (p-1)/4$. Why the split by $p \bmod 8$? The critical quantity $(p-1)/4$ has an integer part depending on $p \bmod 4$, but the exact integer part (and thus the parity of $\mu$) also depends on the next binary digit, so we must look one level finer: modulo $8$. The four cases give a $4$-periodic sign function, which one then recognises as $(-1)^{(p^2-1)/8}$. Finally, why does $\mu \equiv (p^2 - 1)/8 \pmod 2$? We verified this case by case. A cleaner perspective: the map $p \mapsto (-1)^{(p^2-1)/8}$ is multiplicative in $p$ modulo $8$ (for odd integers), takes values $+1, -1, -1, +1$ on $p \equiv 1, 3, 5, 7 \pmod 8$, and so matches the pattern of $(-1)^\mu$ computed above. Both "patterns" are completely determined by $p \bmod 8$, so a case check is a valid proof. [/guided] [/step]