0
$\begingroup$

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.

$\endgroup$

marked as duplicate by Daniel Fischer, Hakim, Namaste, Umberto P., Davide Giraudo Jun 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
$\begingroup$

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

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

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

$\endgroup$
  • $\begingroup$ I wouldn't have come up with this neither, so don't worry. It's just a trick. $\endgroup$ – punctured dusk Jun 6 '14 at 18:06
  • $\begingroup$ Perhaps a clever trick when it was first used, but from a group-theoretic point of view structurally very natural. $\endgroup$ – André Nicolas Jun 6 '14 at 18:14
  • $\begingroup$ 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. $\endgroup$ – punctured dusk Jun 6 '14 at 18:23
  • $\begingroup$ 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$. $\endgroup$ – André Nicolas Jun 6 '14 at 18:35
  • $\begingroup$ 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! $\endgroup$ – punctured dusk Jun 6 '14 at 18:40

Not the answer you're looking for? Browse other questions tagged or ask your own question.