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
and is a quadratic non-residue modulo $p$ if and only if
|||I.M. Vinogradov, "Elements of number theory" , Dover, reprint (1954) (Translated from Russian)|
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.
|[a1]||G.H. Hardy, E.M. Wright, "An introduction to the theory of numbers" , Oxford Univ. Press (1979) pp. Chapt. XIII|
Quadratic residue. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Quadratic_residue&oldid=33286