$$\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?
  • 1
    $\begingroup$ 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. $\endgroup$ – Geoff Robinson Jun 22 '14 at 13:57
  • $\begingroup$ @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?? $\endgroup$ – evinda Jun 22 '14 at 14:22
  • $\begingroup$ @GeoffRobinson Do you maybe know how I could prove the inverse? $\endgroup$ – evinda Jun 22 '14 at 19:48
  • $\begingroup$ 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. $\endgroup$ – Geoff Robinson Jun 22 '14 at 22:11
  • $\begingroup$ @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? $\endgroup$ – 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$.

  • $\begingroup$ And how to we conclude from this that $p=4k+1$ ? $\endgroup$ – evinda Jun 22 '14 at 13:50
  • $\begingroup$ 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 $\endgroup$ – Mathmo123 Jun 22 '14 at 13:51
  • 1
    $\begingroup$ 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. $\endgroup$ – Ian Mateus Jun 22 '14 at 13:55
  • $\begingroup$ I haven't really understood why the prime $p$ cannot be of the form $4k+3$..Could you explain it further to me???? $\endgroup$ – evinda Jun 22 '14 at 14:23
  • $\begingroup$ @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$. $\endgroup$ – Ian Mateus Jul 1 '14 at 19:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.