# the solutions are quadratic nonresidues modulo $p$

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

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

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$.
• 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! Nov 20, 2021 at 20:52