Assume: $p$ is a prime that satisfies $p \equiv 3 \pmod 4$

Show: $x^{2} \equiv -1 \pmod p$ has no solutions $\forall x \in \mathbb{Z}$.

I know this problem has something to do with Fermat's Little Theorem, that $a^{p-1} \equiv 1\pmod p$. I tried to do a proof by contradiction, assuming the conclusion and showing some contradiction but just ran into a wall. Any help would be greatly appreciated.

  • $\begingroup$ Suppose $a$ is a generator (a.k.a. primitive root). Can you find $y$ so that $-1 = a^y \pmod p$? Alternatively, consider $a=x$ $\endgroup$ – Hurkyl May 7 '12 at 1:05
  • $\begingroup$ It's related to Euler's criterion. $\endgroup$ – lhf May 7 '12 at 1:06
  • 1
    $\begingroup$ $\LaTeX$ tip: \pmod{p} produces $\pmod{p}$. No need to jump in and out of math mode for it. $\endgroup$ – Arturo Magidin May 7 '12 at 1:11
  • $\begingroup$ Is there a name to this theorem? $\endgroup$ – Vee Hua Zhi Mar 21 '18 at 1:31
  • $\begingroup$ @Vee I believe it is Euler's Criterion but if it was something like _________ Theorem then I do not know. $\endgroup$ – Mr Pie Jun 18 '18 at 11:46

Suppose $x^2\equiv -1\pmod{p}$. Then $x^4\equiv 1\pmod{p}$. That Since $p = 4k+3$, we have $$x^{p-1} = x^{4k+2} = x^2x^{4k} \equiv -1(x^4)^k\equiv -1\pmod{p},$$ which contradicts Fermat's Little Theorem.


Hint $ $ $\rm mod\ P\! = 4K\!+\!3\!:\;$ $\rm\ X^2 \equiv -1 \;\Rightarrow\; 1\equiv X^{P-1} \equiv (X^2)^{2K+1}\equiv (-1)^{2K+1} \equiv -1$

Alternatively, note $\rm\ X^4\equiv 1\equiv X^{4K+2}\Rightarrow\: 1 \equiv X^{\:\!(4,4K+2)}\equiv X^2\equiv -1\:\Rightarrow\: P\:|\:2\: \Rightarrow\Leftarrow$

For the converse, and a group-theoretic viewpoint, see here.


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.