Quadratic residue

modulo $m$

An integer $a$ for which the congruence

$$x^2\equiv a\pmod m$$

is solvable. If the above congruence is unsolvable, then $a$ is called a quadratic non-residue modulo $m$. Euler's criterion: Let $p>2$ be prime. Then an integer $a$ coprime with $p$ is a quadratic residue modulo $p$ if and only if

$$a^{(p-1)/2}\equiv1\pmod p,$$

and is a quadratic non-residue modulo $p$ if and only if

$$a^{(p-1)/2}\equiv-1\pmod p.$$

References

[1]	I.M. Vinogradov, "Elements of number theory" , Dover, reprint (1954) (Translated from Russian)

Comments

An amusing unsolved problem is the following: Let $p$ be a prime with $p\equiv3$ ($\bmod\,4$). Let $N$ be the sum of all quadratic non-residues between 0 and $p$, and $Q$ the sum of all quadratic residues. It is known that $N>Q$. Give an elementary proof.

References

[a1]	G.H. Hardy, E.M. Wright, "An introduction to the theory of numbers" , Oxford Univ. Press (1979) pp. Chapt. XIII