If p is a prime number of the form $4n+3$, show that we cannot solve $x^2\equiv -1\mod p$

Question

Hint: Use Fermat's Theorem that $a^{p-1}\equiv 1\mod p$ if $p \nmid a$. (I have no idea, but something in group theory should help)

Answer 1

The right theorem is that $x^2\equiv -1\pmod{p}$ has no solution if $p$ is of the form $4k+3$. Or equivalently that $x^2+1\equiv 0\pmod{p}$ has no solution.

Let $p=4k+3$.

Note that if $x$ is not divisible by $p$, then
$$(x^2)^{2k+1}=x^{4k+2}\equiv 1\pmod{p}\tag{1}$$ by Fermat's Theorem.

But if $x^2\equiv -1\pmod{p}$, then $$(x^2)^{2k+1}\equiv (-1)^{2k+1}\equiv -1\pmod{p}.$$ Since we cannot have $-1\equiv 1\pmod{p}$, this contradicts (1).

Answer 2

The question is wrong dude. You will NOT be able to solve $x^2\equiv a\pmod p$ is $\left(\frac{a}{p}\right)\equiv -1\pmod p\implies a^{(p-1)/2}\equiv -1\pmod p$ This could help classify the solvable congruences. And your question is wrong because $x\equiv 1\pmod p$works. $1$ is a quadratic residue mod every prime. And $(-1)^{(p-1)/2}\equiv (-1)^{2n+1}\equiv -1\pmod p$ hence $x^2\equiv -1\pmod p$ is not solvable.

Answer 3

Yes, you have a typo. (Otherwise just take $x \equiv \pm 1 \pmod p$.)

If you mean $x^2+1 \equiv 0$ is unsolvable, then here is a sketch of the proof.

Say $p\equiv3\pmod4$ and $p|a^2+b^2$. Then from Fermat's theorem, $p|a^{p-1}-b^{p-1}$. On the other hand, since $\dfrac{p-1}2$ odd, $p|a^2+b^2|\left(a^2\right)^{\frac{p-1}2}+\left(b^2\right)^{\frac{p-1}2}=a^{p-1}+b^{p-1}$. Thus $p|2a^{p-1}$ implying $p|a,b$. Therefore, $p$ must divide $a,b$ and the conclusion follows.

Answer 4

A group theory flavoured hinted solution:

First, we can reduce the problem to showing there doesn't exists $\;x\in\Bbb F_p\cong\Bbb Z/p\Bbb Z\;$ s.t. $\;x^2=-1\;$ by passing from the integers (usual) arithmetic to arithmetic modulo $\;p\;$.

Second, since $\;x=0\in\Bbb F_p\implies x^2=0\neq-1\;$ , we can in fact assume we're working within the cyclic group $\;\Bbb F_p^*:=\Bbb F_p\setminus\{0\}\;$.

Now, suppose

$$\exists\,x\in\Bbb F_p^*\;\;s.t.\;\;x^2=-1\implies x^4=1$$

and since clearly $\;x\neq 1\;$ (why?), we've then found an element of order four in $\;\Bbb F_p^*\;$ ....but this is absurd (why? Complete the proof).