Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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$ – Hurkyl May 7 '12 at 1:05
It's related to Euler's criterion. – lhf May 7 '12 at 1:06
$\LaTeX$ tip: \pmod{p} produces $\pmod{p}$. No need to jump in and out of math mode for it. – Arturo Magidin May 7 '12 at 1:11
up vote 13 down vote accepted

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.

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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