Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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
1  
$\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

2 Answers 2

up vote 12 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|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|improve this answer

Your Answer

 
discard

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.