11
$\begingroup$

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.

  • 0
    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$2012-05-07
  • 0
    It's related to [Euler's criterion](http://en.wikipedia.org/wiki/Euler's_criterion).2012-05-07
  • 1
    $\LaTeX$ tip: `\pmod{p}` produces $\pmod{p}$. No need to jump in and out of math mode for it.2012-05-07
  • 0
    Is there a name to this theorem?2018-03-21
  • 0
    @Vee I believe it is **Euler's Criterion** but if it was something like **_________ Theorem** then I do not know.2018-06-18
  • 0
    Thanks @user477343 I wanted to use it in a proof and I wanted to state the name of it2018-06-18

2 Answers 2

25

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.

0

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.