# 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?
• You want to get your answer in the interval $(1,p-1).$ In fact, you can get $x \in (1,\frac{p-1}{2}).$ Remember, it is only the answer (mod $p$) that is important. The answer $18!$ is correct (mod $37$) but $18!$ is a ridiculously large integer, and you should try to simplify it. – Geoff Robinson Jun 22 '14 at 13:57
• @GeoffRobinson Do you mean that I have to write $18!$ like that:$1 \cdot 2 \cdots 18$ and then simplify the numbers?Also are $14! \text{ and } 18!,$ the only solutions of $x^2+1 \equiv 0 \pmod{29} \text{ and } x^2+1 \equiv 0 \pmod{37}$ respectively?? – evinda Jun 22 '14 at 14:22
• @GeoffRobinson Do you maybe know how I could prove the inverse? – evinda Jun 22 '14 at 19:48
• Hint for last question If $x^{2} = -1$, then $x$ has multiplicative order $4$ in the group of non-zero elements of the field under multiplication. Yes,, you should simplify the factorials, though from a theoretical point of view it is not essential. Second question, the answer are $\pm 14!$ and $\pm 18!$ respectively. – Geoff Robinson Jun 22 '14 at 22:11
• @GeoffRobinson I haven't get taught multiplicative orders...Isn't there an other way to show it? And why do we know that there are only these 2 solutions? – evinda Jun 22 '14 at 22:24

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$.
• And how to we conclude from this that $p=4k+1$ ? – evinda Jun 22 '14 at 13:50
• If $p \equiv -1$ (mod $4$), then if $x^2 \equiv -1$ (mod $p$), then $-1 \equiv (-1)^{\frac{p-1}{2}} \equiv x^{p-1} \equiv 1$ (mod $p$) by Fermat's Little Theorem - a contradiction – Mathmo123 Jun 22 '14 at 13:51
• You have already used the condition $p=4k+1$. If $p=4k+3$, you will get $\left(\frac{p-1}{2}\right)!^2\equiv 1\pmod p$, not really helpful. There are actually no solutions to $x^2\equiv -1\pmod p$ if $p=4k+3$, but you will probably use a bit different route to show that. – Ian Mateus Jun 22 '14 at 13:55
• I haven't really understood why the prime $p$ cannot be of the form $4k+3$..Could you explain it further to me???? – evinda Jun 22 '14 at 14:23
• @evinda If $p\equiv 3 \pmod 4$, there are no solutions to $x^2\equiv -1\pmod p$. We say that $-1$ is a quadratic nonresidue modulo $p$. I don't know how much number theory you have seen, but it shouldn't be too difficult to you to learn Euler's criterion and then show (using the Legendre symbol) $$\left(\frac{-1}{p}\right)\equiv (-1)^{(p-1)/2} \pmod p.$$ That is, $-1$ is a quadratic nonresidue modulo $p$ if $p\equiv 3\pmod 4$. – Ian Mateus Jul 1 '14 at 19:03