16
$\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.

$\endgroup$
6
  • $\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$
    – user14972
    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$ May 7 '12 at 1:11
  • $\begingroup$ Is there a name to this theorem? $\endgroup$ 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
40
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
0
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

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.