<s>[INST] For an odd prime $p$, $\;p =1 \pmod 4,\; \;x^2+1 = 0 \pmod p$ $$\text{ If } p \neq 2 \text{ is a prime, we know that: }$$
$$\left(\left(\frac{p-1}{2}\right)!\right)^2 \equiv (-1)^{\frac{p+1}{2}} \pmod p$$
According to this,prove that:
$$p \equiv 1 \pmod 4 \Rightarrow x^2+1\equiv 0 \pmod p \text{ has a solution}$$
$$\text{Which is the solution?}$$
Solve: $\displaystyle{ x^2+1 \equiv 0 \pmod{29} \text{ , } x^2+1 \equiv 0 \pmod{37}}$
Inversely,prove that $x^2+1 \equiv 0 \pmod p \text{ has a solution } \Rightarrow p \equiv 1 \pmod 4$
I have thought the following:


*

*$$\left(\left(\frac{p-1}{2}\right)!\right)^2-(-1)^{\frac{p+1}{2}} \equiv 0 \pmod p \Rightarrow \left(\left(\frac{p-1}{2}\right)!\right)^2+(-1)^{\frac{p+3}{2}} \equiv 0 \pmod p $$


As $p=4k+1$, $(-1)^{\frac{p+3}{2}}=(-1)^{\frac{4k+4}{2}}=1$
So,we have: $$\left(\left(\frac{p-1}{2}\right)!\right)^2+1 \equiv 0 \pmod p$$
So,we conclude that $x^2+1 \equiv 0 \pmod p \text{ has a solution , this one: } (\frac{p-1}{2})!$
Is it right or have I done something wrong?


*

*So,are the solutions of $x^2+1 \equiv 0 \pmod{29} \text{ and } x^2+1 \equiv 0 \pmod{37}$,these one: $\displaystyle{(14)! \text{ and } (18)! \text{ respectively}}$ ?
Are these the only solutions??

*How can I show the inverse? 

 [/INST] That seems correct to me. The last part comes from the fact that the equation $x^2 +1 \equiv 0$ (mod $p$) has at most 2 distinct solutions because it is a degree 2 polynomial and $p$ is prime. And if $x$ is a solution, then so is $-x$.
</s>