Namespaces
Variants
Actions

Difference between revisions of "Quadratic residue"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(TeX)
 
Line 1: Line 1:
''modulo <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076140/q0761402.png" />''
+
{{TEX|done}}
 +
''modulo $m$''
  
An integer <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076140/q0761403.png" /> for which the [[Congruence|congruence]]
+
An integer $a$ for which the [[Congruence|congruence]]
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076140/q0761404.png" /></td> </tr></table>
+
$$x^2\equiv a\pmod m$$
  
is solvable. If the above congruence is unsolvable, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076140/q0761405.png" /> is called a quadratic non-residue modulo <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076140/q0761407.png" />. Euler's criterion: Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076140/q0761408.png" /> be prime. Then an integer <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076140/q0761409.png" /> coprime with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076140/q07614010.png" /> is a quadratic residue modulo <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076140/q07614011.png" /> if and only if
+
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
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076140/q07614012.png" /></td> </tr></table>
+
$$a^{(p-1)/2}\equiv1\pmod p,$$
  
and is a quadratic non-residue modulo <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076140/q07614013.png" /> if and only if
+
and is a quadratic non-residue modulo $p$ if and only if
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076140/q07614014.png" /></td> </tr></table>
+
$$a^{(p-1)/2}\equiv-1\pmod p.$$
  
 
====References====
 
====References====
Line 19: Line 20:
  
 
====Comments====
 
====Comments====
An amusing unsolved problem is the following: Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076140/q07614015.png" /> be a prime with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076140/q07614016.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076140/q07614017.png" />). Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076140/q07614018.png" /> be the sum of all quadratic non-residues between 0 and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076140/q07614019.png" />, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076140/q07614020.png" /> the sum of all quadratic residues. It is known that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076140/q07614021.png" />. Give an elementary proof.
+
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====
 
====References====
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  G.H. Hardy,  E.M. Wright,  "An introduction to the theory of numbers" , Oxford Univ. Press  (1979)  pp. Chapt. XIII</TD></TR></table>
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  G.H. Hardy,  E.M. Wright,  "An introduction to the theory of numbers" , Oxford Univ. Press  (1979)  pp. Chapt. XIII</TD></TR></table>

Latest revision as of 13:35, 14 September 2014

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=11386
This article was adapted from an original article by S.A. Stepanov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article