[proofplan] The result follows from [Euler's Criterion](/theorems/???), which evaluates the Legendre symbol as $\left(\frac{-1}{p}\right) \equiv (-1)^{(p-1)/2} \pmod{p}$. Since $p$ is odd, write $p = 4k + l$ with $l \in \{1, 3\}$; then the parity of $(p-1)/2$ is controlled by $l$, giving $+1$ when $p \equiv 1 \pmod 4$ and $-1$ when $p \equiv 3 \pmod 4$. Finally we upgrade the congruence mod $p$ to an equality in $\{\pm 1\}$ using that $p$ is odd. [/proofplan] [step:Apply Euler's criterion to rewrite the Legendre symbol] The hypothesis is that $p$ is an odd prime. We apply [Euler's Criterion](/theorems/???): for an odd prime $p$ and any $a \in \mathbb{Z}$, \begin{align*} \left(\frac{a}{p}\right) \equiv a^{(p-1)/2} \pmod{p}. \end{align*} The criterion requires only that $p$ be an odd prime, which is given. Taking $a = -1$, \begin{align*} \left(\frac{-1}{p}\right) \equiv (-1)^{(p-1)/2} \pmod{p}. \end{align*} [/step] [step:Determine the parity of the exponent from the residue class of $p$ modulo $4$] Since $p$ is an odd prime, $p$ is odd, so $p \equiv 1$ or $p \equiv 3 \pmod 4$. Write $p = 4k + l$ with $k \in \mathbb{Z}_{\ge 0}$ and $l \in \{1, 3\}$. Then \begin{align*} \frac{p - 1}{2} = \frac{4k + l - 1}{2} = 2k + \frac{l - 1}{2}. \end{align*} We evaluate the second summand in each case. If $l = 1$, then $(l-1)/2 = 0$, so $(p-1)/2 = 2k$ is even. If $l = 3$, then $(l-1)/2 = 1$, so $(p-1)/2 = 2k + 1$ is odd. Consequently \begin{align*} (-1)^{(p-1)/2} = \begin{cases} +1 & \text{if } p \equiv 1 \pmod{4}, \\ -1 & \text{if } p \equiv 3 \pmod{4}. \end{cases} \end{align*} [/step] [step:Upgrade the congruence modulo $p$ to an equality of integers] Combining the previous two steps, \begin{align*} \left(\frac{-1}{p}\right) \equiv \begin{cases} +1 & p \equiv 1 \pmod{4}, \\ -1 & p \equiv 3 \pmod{4}, \end{cases} \pmod{p}. \end{align*} Both sides lie in the set $\{+1, -1\}$: the left side by definition of the Legendre symbol for $a = -1$ coprime to $p$, and the right side by construction. The difference of any two distinct elements of $\{+1, -1\}$ is $\pm 2$, and $p \nmid 2$ because $p$ is odd. Hence a congruence modulo $p$ between two elements of $\{+1, -1\}$ forces equality as integers. [guided] We have shown \begin{align*} \left(\frac{-1}{p}\right) \equiv (-1)^{(p-1)/2} \pmod{p}, \end{align*} and that the right-hand side equals $+1$ when $p \equiv 1 \pmod 4$ and $-1$ when $p \equiv 3 \pmod 4$. How do we pass from a congruence to an equality? The issue is that in principle a congruence $x \equiv y \pmod p$ leaves room for $x - y = kp$ with $k \ne 0$. We rule this out by showing both $x$ and $y$ take values in the two-element set $\{+1, -1\}$. The left-hand side $\left(\frac{-1}{p}\right)$ lies in $\{+1, -1\}$ because $p \nmid -1$ (so $-1$ is a unit modulo $p$), and the Legendre symbol of a unit is $\pm 1$ by definition. The right-hand side $(-1)^{(p-1)/2}$ lies in $\{+1, -1\}$ by construction. Now if $x, y \in \{+1, -1\}$ and $x \equiv y \pmod p$, then $x - y \in \{-2, 0, +2\}$. Since $p$ is odd, $p \nmid 2$, so $p \mid (x - y)$ forces $x - y = 0$, i.e. $x = y$. This is precisely where the hypothesis "$p$ odd" is consumed a second time (the first was in applying Euler's criterion). Therefore \begin{align*} \left(\frac{-1}{p}\right) = \begin{cases} +1 & \text{if } p \equiv 1 \pmod{4}, \\ -1 & \text{if } p \equiv 3 \pmod{4}, \end{cases} \end{align*} as an identity of integers, completing the proof. [/guided] [/step]