Quadratic residue
From Encyclopedia of Mathematics
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.
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 |
How to Cite This Entry:
Quadratic residue. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Quadratic_residue&oldid=33286
Quadratic residue. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Quadratic_residue&oldid=33286
This article was adapted from an original article by S.A. Stepanov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article