Here is the question :

Prove that if the prime $p\equiv 1\pmod4$ and $q$ is a quadratic nonresidue mod $p$, then the solutions of the congruence $x^2 \equiv -1\pmod p$ are $x\equiv \pm q^a\pmod p$, where $a=\frac{p-1}{4}$.

I don't know where to begin, a hint would be appreciated thank you.


You're given what the solutions are - to check that they are solutions, plug them in.

Keep in mind Euler's criterion.

  • $\begingroup$ If we plug in the solutions, then we get a congruence of the form as suggested in Euler's criteria which is equivalent to the legendre's symbol $\left(\frac ap\right)$,(where $a = -1$) hence proving that the solutions are the ones given in the equation.Is this simply the answer?Am I right? $\endgroup$ – Paradox 101 Nov 10 '14 at 8:52
  • $\begingroup$ No, you get the Legendre symbol $\left(\frac{q}{p}\right)$. Which is $-1$ by the definition of the Legendre symbol. You do not get the Legendre symbol $\left(\frac{-1}{p}\right)$. $\endgroup$ – curious Nov 10 '14 at 8:56
  • $\begingroup$ Also, this proves that $\pm q^a$ are some solutions. Do you understand why there can't be any others? (Or moreover that the numbers $\pm q^a$ don't depend on which quadratic non-residue $q$ you start with?) $\endgroup$ – curious Nov 10 '14 at 8:58
  • $\begingroup$ Oh, I'm sorry you're right it's $q$ not $-1$. But if the legendre's symbol is $-1$, shouldn't there be no solutions at all? Because q is a quadratic nonresidue? $\endgroup$ – Paradox 101 Nov 10 '14 at 9:08
  • 1
    $\begingroup$ $$x=q^{(p-1)/4}\text{ is a solution to }x^2\equiv -1\bmod p\\\\ \iff (q^{(p-1)/4})^2\equiv -1\bmod p\\\\ \iff q^{(p-1)/2}\equiv -1\bmod p\\\\ \iff \left(\frac{q}{p}\right)\equiv -1\bmod p\\\\ \iff q\text{ is a quadratic non-residue mod }p$$ which is what we said about $q$ from the beginning. $\endgroup$ – curious Nov 10 '14 at 9:11

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.