[proofplan] We apply [Euler's criterion](/theorems/1715) to the integer $a=-1$, which is coprime to the odd prime $p$. This gives a congruence modulo $p$ between the [Legendre symbol](/page/Legendre%20Symbol) $\left(\frac{-1}{p}\right)$ and $(-1)^{(p-1)/2}$. Since both sides are ordinary integers in $\{-1,1\}$, the congruence forces equality. The two congruence classes of $p$ modulo $4$ then determine the parity of $(p-1)/2$. [/proofplan]

[step:Apply Euler's criterion to the integer $-1$]Let \begin{align*} e:=\frac{p-1}{2}. \end{align*} Since $p$ is an odd prime, $p \nmid -1$, so Euler's criterion applies to $a=-1$. Euler's criterion states that, for an odd prime $p$ and an integer $a$ with $p \nmid a$, \begin{align*} \left(\frac{a}{p}\right)\equiv a^{(p-1)/2}\pmod p. \end{align*} Applying it with $a=-1$ gives \begin{align*} \left(\frac{-1}{p}\right)\equiv (-1)^e \pmod p. \end{align*}[/step]

[guided]Let \begin{align*} e:=\frac{p-1}{2}. \end{align*} This is an integer because $p$ is odd. We want to compute the Legendre symbol $\left(\frac{-1}{p}\right)$, and Euler's criterion is designed exactly for this: it converts the Legendre symbol into a power modulo $p$. Euler's criterion says that if $p$ is an odd prime and $a \in \mathbb{Z}$ satisfies $p \nmid a$, then \begin{align*} \left(\frac{a}{p}\right)\equiv a^{(p-1)/2}\pmod p. \end{align*} We verify its hypothesis for $a=-1$. Since no prime divides $1$, and $p \mid -1$ would imply $p \mid 1$, we have $p \nmid -1$. Therefore Euler's criterion applies and gives \begin{align*} \left(\frac{-1}{p}\right)\equiv (-1)^{(p-1)/2}\pmod p. \end{align*} Using the definition of $e$, this is \begin{align*} \left(\frac{-1}{p}\right)\equiv (-1)^e \pmod p. \end{align*}[/guided]

[step:Convert the congruence modulo $p$ into equality of integers] The Legendre symbol $\left(\frac{-1}{p}\right)$ lies in $\{-1,1\}$ because $p \nmid -1$. Also $(-1)^e \in \{-1,1\}$. Define \begin{align*} u:=\left(\frac{-1}{p}\right)-(-1)^e. \end{align*} The preceding congruence says $p \mid u$, while $u \in \{-2,0,2\}$. Since $p$ is an odd prime, $p \geq 3$, so $p \nmid 2$ and $p \nmid -2$. Hence $u=0$, and therefore \begin{align*} \left(\frac{-1}{p}\right)=(-1)^e=(-1)^{(p-1)/2}. \end{align*} [/step]

[step:Read off the two residue classes modulo $4$] If $p \equiv 1 \pmod 4$, then there exists $m \in \mathbb{Z}$ such that $p=4m+1$. Hence \begin{align*} \frac{p-1}{2}=2m, \end{align*} so $(p-1)/2$ is even and \begin{align*} \left(\frac{-1}{p}\right)=(-1)^{(p-1)/2}=1. \end{align*} If $p \equiv 3 \pmod 4$, then there exists $m \in \mathbb{Z}$ such that $p=4m+3$. Hence \begin{align*} \frac{p-1}{2}=2m+1, \end{align*} so $(p-1)/2$ is odd and \begin{align*} \left(\frac{-1}{p}\right)=(-1)^{(p-1)/2}=-1. \end{align*} This proves both the formula and its two stated congruence cases. [/step]