Constructive proof for $p|x^2+1$ It's easy to prove $x^2+1$ is never divisible by $4k+3$ primes. I know a non-constructive proof for existing $x$ so that $p|x^2+1$ for $4k+1$ primes. is there any constructive one?

First note that
$(p-1)! = -1 \mod p$
by Wilson's Theorem. Since $p = 4k+ 1$, we can write this product as
$1\cdot 2 \cdots (\frac{p-1}{2}) (\frac{p+1}{2}) \cdots (p-1) \equiv -1 \mod p$
Note that this can be written as
$1 \cdot 2 \cdots (\frac{p-1}{2}) \cdot (p-\frac{p-1}{2}) \cdots (p-1) \equiv -1 \mod p$
so
$1 \cdot 2 \cdots (\frac{p-1}{2}) \cdot (-\frac{p-1}{2}) \cdots (-1) \equiv -1 \mod p$
so
$(\frac{p-1}{2})^2 \cdot (-1)^{\frac{p-1}{2}} \equiv -1 \mod p$
Since $p \equiv 1 \mod 4$, $\frac{p-1}{2}$ is even. Thus we are left with
$(\frac{p-1}{2})^2 \equiv -1 \mod 2$.
