[proofplan] We prove the two implications separately. When $p \equiv 1 \pmod{4}$, [Wilson's theorem](/theorems/733) rewrites $(p-1)!$ as a signed square, and the sign is positive because $\frac{p-1}{2}$ is even. When $p \equiv 3 \pmod{4}$, any putative square root $z$ of $-1$ is nonzero modulo $p$, so [Fermat's little theorem](/theorems/731) forces $1 \equiv -1 \pmod{p}$, contradicting that $p$ is odd. [/proofplan] [step:Use Wilson's theorem to construct a square root when $p \equiv 1 \pmod{4}$] Assume $p \equiv 1 \pmod{4}$. Since $p$ is an odd prime and $p \equiv 1 \pmod{4}$, there exists an integer $k \geq 1$ such that $p = 4k + 1$. Define the integer \begin{align*} m := \frac{p - 1}{2} = 2k. \end{align*} By Wilson's theorem, because $p$ is prime, \begin{align*} (p - 1)! \equiv -1 \pmod{p}. \end{align*} Split the factorial at $m$: \begin{align*} (p - 1)! = \prod_{a=1}^{m} a \prod_{j=m+1}^{p-1} j. \end{align*} For every integer $j$ with $m+1 \leq j \leq p-1$, set $a := p-j$. Then $1 \leq a \leq m$ and $j \equiv -a \pmod{p}$. Therefore \begin{align*} \prod_{j=m+1}^{p-1} j \equiv \prod_{a=1}^{m} (-a) = (-1)^m m! \pmod{p}. \end{align*} Multiplying by the first half of the factorial gives \begin{align*} (p - 1)! \equiv m! \cdot (-1)^m m! = (-1)^m (m!)^2 \pmod{p}. \end{align*} Since $m = 2k$ is even, $(-1)^m = 1$. Combining this congruence with Wilson's theorem yields \begin{align*} -1 \equiv (p - 1)! \equiv (m!)^2 \pmod{p}. \end{align*} Thus the integer $x := m!$ satisfies $x^2 \equiv -1 \pmod{p}$. [guided] Assume $p \equiv 1 \pmod{4}$. Since $p$ is an odd prime and is congruent to $1$ modulo $4$, we may write \begin{align*} p = 4k + 1 \end{align*} for some integer $k \geq 1$. Define \begin{align*} m := \frac{p - 1}{2}. \end{align*} Then $m = 2k$, so $m$ is even. We now use Wilson's theorem. Its hypothesis is that $p$ is prime, which is part of the theorem statement. Hence \begin{align*} (p - 1)! \equiv -1 \pmod{p}. \end{align*} The purpose of the next computation is to express $(p-1)!$ as a square modulo $p$. Split the product into the first and second halves: \begin{align*} (p - 1)! = \prod_{a=1}^{m} a \prod_{j=m+1}^{p-1} j. \end{align*} For a factor $j$ in the second product, define $a := p-j$. Since $m+1 \leq j \leq p-1$, we have $1 \leq a \leq p-(m+1)=m$. Also, \begin{align*} j = p-a \equiv -a \pmod{p}. \end{align*} As $j$ runs from $m+1$ to $p-1$, the integer $a=p-j$ runs through $m,m-1,\dots,1$. Reordering a finite product does not change its value, so the second half of the factorial satisfies \begin{align*} \prod_{j=m+1}^{p-1} j \equiv \prod_{a=1}^{m} (-a) = (-1)^m m! \pmod{p}. \end{align*} Substituting this into the split factorial gives \begin{align*} (p - 1)! \equiv \left(\prod_{a=1}^{m} a\right)\left(\prod_{a=1}^{m} (-a)\right) = m! \cdot (-1)^m m! = (-1)^m (m!)^2 \pmod{p}. \end{align*} Because $m=2k$ is even, $(-1)^m=1$. Therefore \begin{align*} (p - 1)! \equiv (m!)^2 \pmod{p}. \end{align*} Combining this with Wilson's theorem gives \begin{align*} -1 \equiv (p - 1)! \equiv (m!)^2 \pmod{p}. \end{align*} Thus $x := m!$ is an integer with $x^2 \equiv -1 \pmod{p}$, so $-1$ is a [quadratic residue](/pages/quadratic-residue) modulo $p$. [/guided] [/step] [step:Use Fermat's little theorem to rule out a square root when $p \equiv 3 \pmod{4}$] Assume $p \equiv 3 \pmod{4}$. Then there exists an integer $k \geq 0$ such that $p = 4k + 3$. Suppose, for contradiction, that there exists $z \in \mathbb{Z}$ such that \begin{align*} z^2 \equiv -1 \pmod{p}. \end{align*} Then $p \nmid z$, because $p \mid z$ would imply $z^2 \equiv 0 \pmod{p}$ and hence $0 \equiv -1 \pmod{p}$, so $p \mid 1$, impossible for a prime. By Fermat's little theorem, applied to the integer $z$ with $p \nmid z$, \begin{align*} z^{p-1} \equiv 1 \pmod{p}. \end{align*} Using $p-1 = 4k+2$ and $z^2 \equiv -1 \pmod{p}$, \begin{align*} z^{p-1} = z^{4k+2} = (z^2)^{2k+1} \equiv (-1)^{2k+1} = -1 \pmod{p}. \end{align*} Thus $1 \equiv -1 \pmod{p}$, so $p \mid 2$. This contradicts that $p$ is an odd prime. Therefore no integer $z$ satisfies $z^2 \equiv -1 \pmod{p}$ when $p \equiv 3 \pmod{4}$. [guided] Assume $p \equiv 3 \pmod{4}$. Then \begin{align*} p = 4k + 3 \end{align*} for some integer $k \geq 0$. We argue by contradiction. Suppose there exists an integer $z \in \mathbb{Z}$ such that \begin{align*} z^2 \equiv -1 \pmod{p}. \end{align*} Before applying Fermat's little theorem, we must check its coprimality hypothesis. If $p \mid z$, then $z^2 \equiv 0 \pmod{p}$. Combining this with $z^2 \equiv -1 \pmod{p}$ would give \begin{align*} 0 \equiv -1 \pmod{p}, \end{align*} so $p \mid 1$, which is impossible for a prime. Hence $p \nmid z$. Fermat's little theorem now applies to $z$, because $p$ is prime and $p \nmid z$. It gives \begin{align*} z^{p-1} \equiv 1 \pmod{p}. \end{align*} On the other hand, the assumed congruence $z^2 \equiv -1 \pmod{p}$ lets us compute the same power using the fact that $p-1=4k+2$: \begin{align*} z^{p-1} = z^{4k+2} = (z^2)^{2k+1} \equiv (-1)^{2k+1} = -1 \pmod{p}. \end{align*} The exponent $2k+1$ is odd, which is why the final value is $-1$ rather than $1$. Thus the same integer $z^{p-1}$ is congruent to both $1$ and $-1$ modulo $p$, so \begin{align*} 1 \equiv -1 \pmod{p}. \end{align*} Equivalently, $p \mid 2$. Since $p$ is an odd prime, $p \geq 3$, and no prime $p \geq 3$ divides $2$. This contradiction shows that no integer $z$ can satisfy $z^2 \equiv -1 \pmod{p}$ when $p \equiv 3 \pmod{4}$. [/guided] [/step] [step:Combine the two congruence classes modulo $4$] Since $p$ is an odd prime, $p$ is not divisible by $2$. Hence its residue modulo $4$ is either $1$ or $3$. The first step proves that if $p \equiv 1 \pmod{4}$, then there exists $x \in \mathbb{Z}$ with $x^2 \equiv -1 \pmod{p}$. The second step proves that if $p \equiv 3 \pmod{4}$, then no such integer exists. Therefore \begin{align*} \exists\, x \in \mathbb{Z} \text{ with } x^2 \equiv -1 \pmod{p} \quad \iff \quad p \equiv 1 \pmod{4}. \end{align*} [/step]