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.

• 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? – Paradox 101 Nov 10 '14 at 8:52
• 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)$. – curious Nov 10 '14 at 8:56
• 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?) – curious Nov 10 '14 at 8:58
• 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? – Paradox 101 Nov 10 '14 at 9:08
• $$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. – curious Nov 10 '14 at 9:11