# Let $p$ be a prime number such that $p \equiv 3 \pmod 4$. Show that $x^2 \equiv -1 \pmod p$ has no solutions. [duplicate]

Let $$p$$ be a prime number such that $$p \equiv 3 \pmod 4$$. Show that $$x^2 \equiv -1 \pmod p$$ has no solutions.

I noticed that this is equivalent to proving $$x^2\equiv 2(2k+1) \pmod p$$. I also know that $$x^2 \neq 2(2k+1)$$. But I still can't prove it. Any help would be greatly appreciated.

## marked as duplicate by Daniel Fischer, Hakim, Namaste, Umberto P., Davide GiraudoJun 6 '14 at 19:27

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

## 2 Answers

If there is an $x$ such that $x^2=-1\pmod p$ then ${\rm ord}_p(x)=4$. Thus $4$ must divide the order of the multiplicative group modulo $p$ which is $p-1$.

• Funny, haven't seen this before! – punctured dusk Jun 6 '14 at 18:21
• This is a standard argument :) – Ted Shifrin Jun 6 '14 at 18:40

Hint: What happens if you raise both sides to the power $\frac{p-1}2$ in the congruence $x^2\equiv-1$?

• I wouldn't have come up with this neither, so don't worry. It's just a trick. – punctured dusk Jun 6 '14 at 18:06
• Perhaps a clever trick when it was first used, but from a group-theoretic point of view structurally very natural. – André Nicolas Jun 6 '14 at 18:14
• How so? Is there a better reason than "raising to the $\frac{p-1}2$th power will limit the possible residues"? I'm curious. – punctured dusk Jun 6 '14 at 18:23
• The order of an element divides the order of the group. For an odd prime $p$, any square root of $-1$ has order $4$. But $4$ does not divide $p-1$ in the case $p=4k+3$. The idea generalizes to $q$-th roots of $1$. – André Nicolas Jun 6 '14 at 18:35
• If I understand well, what you mean is by raising to the $\frac{p-1}2$th power, only elements of order $\leq2$ will give $1$ and so this is actually a disguised form of Omran's answer. Hadn't tought about it this way! – punctured dusk Jun 6 '14 at 18:40