Prove that $x^{2} \equiv -1 \pmod p$ has no solutions if prime $p \equiv 3 \pmod 4$.

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.

• 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$
– user14972
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. May 7 '12 at 1:11
• Is there a name to this theorem? Mar 21 '18 at 1:31
• @Vee I believe it is Euler's Criterion but if it was something like _________ Theorem then I do not know. Jun 18 '18 at 11:46

Suppose $$x^2\equiv -1\pmod{p}$$. Then $$x^4\equiv 1\pmod{p}$$. 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.

It is equivalent to $$\nexists n: \frac{n^2+1}{p}\in \mathbb{N}$$, which is a case of the sum of squares theorem.

Isn't this easier than using FLT. Consider a solution x then x is even or odd. Substituting this into x^2=-1 (mod p) leads to a contradiction in both cases.

Hint $$\bmod P\! = 4K\!+\!3\!:\;$$ $$\ \color{#c00}{X^{\large 2} \equiv -1} \;\Rightarrow\; 1\equiv X^{\large P-1} \equiv (\color{#c00}{X^{\large 2}})^{\large 2K+1}\equiv (\color{#c00}{-1})^{\large 2K+1} \equiv -1$$

Alternatively $$\ X^{\large 4}\equiv 1\equiv X^{\large 4K+2}\Rightarrow\, 1 \equiv X^{\large \,\!(4,\,4K+2)}\equiv X^{\large 2}\equiv -1\,\Rightarrow\, P\mid2\, \Rightarrow\!\Leftarrow$$

Remark  The proof is a special case of Euler's Criterion.

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

A solution to the given congruence would imply there exists an element of multiplicative order 4 in the finite field of size p which is false because (p-1)/2 is odd and therefore p-1 is not divisible by 4.