Quadratic residue

From Encyclopedia of Mathematics
Jump to: navigation, search

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


[1] 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
How to Cite This Entry:
Quadratic residue. Encyclopedia of Mathematics. URL:
This article was adapted from an original article by S.A. Stepanov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article