Let $q$ be an odd prime number, such that $p=4q+1$ is also an odd prime. I want to show that the congruence $x^2 \equiv -1 \pmod{p}$ has two (incongruenct modulo $p$) solutions, which are quadratic nonresidues modulo $p$.

I have thought to consider the Jacobi symbol.

We have that $\left( \frac{-1}{p}\right)=\left( \frac{-1}{4q+1}\right)=(-1)^{\frac{4q+1-1}{2}}=(-1)^{2q}=1$.

From this we deduce that $x^2 \equiv -1 \pmod{p}$ has two incongruent modulo $p$ solutions, right?

How do we deduce that the solutions are quadratic nonresidues modulo $p$ ?

  • 1
    $\begingroup$ Hint: suppose you got quadratic residues. Deduce the existence of an element of order $8$, derive contradiction. $\endgroup$
    – lulu
    Aug 6, 2018 at 20:14

1 Answer 1


Suppose $x$ could be a quadratic residue modulo $p$ then we could write $x\equiv a^2\bmod p$ for some integer $a$ therefore $a^4\equiv -1\bmod p\implies a^{p-1}\equiv (-1)^{\frac{p-1}{4}}\bmod p\implies 1\equiv (-1)^{q}\bmod p$ but since $q$ is an odd prime this means $1\equiv -1\bmod p\implies 2\equiv 0\bmod p\implies p\mid 2\implies p=2$ which is a contradiction. Therefore $x$ must be quadratic non-residue or equivilently $\left( \frac{x}{p}\right)=-1$, and since $\left( \frac{-x}{p}\right)=\left( \frac{-1}{p}\right)\left( \frac{x}{p}\right)=\left( \frac{x}{p}\right)=-1$ we see $-x$ is also a quadratic non-residue, thus all solutions $y$ to the equation $y^2\equiv -1\bmod p$ are quadratic non-residues modulo $p$.

  • $\begingroup$ How did you go from $x\equiv a^2\pmod{p}$ to $a^4\equiv -1\pmod{p}?$ Sorry I know this is very outdated! $\endgroup$
    – BoostMatch
    Nov 20, 2021 at 20:52

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.