Namespaces
Variants
Actions

Difference between revisions of "Euler criterion"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(LaTeX)
Line 1: Line 1:
If an integer <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036430/e0364301.png" /> is not divisible by a prime number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036430/e0364302.png" />, then the congruence
+
{{TEX|done}}
 +
If an integer $a$ is not divisible by a prime number $p>2$, then the congruence
 +
$$
 +
a^{(p-1)/2} \equiv \left({\frac{a}{p}}\right) \pmod p
 +
$$
 +
holds, where $\left({\frac{a}{p}}\right)$ is the [[Legendre symbol]]. Thus, the Euler criterion gives a necessary and sufficient condition for a number $a \not\equiv 0 \pmod p$ to be a [[quadratic residue]] or non-residue modulo $p$. It was proved by L. Euler in 1761 (see [[#References|[1]]]).
  
<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/e/e036/e036430/e0364303.png" /></td> </tr></table>
+
Euler also obtained a more general result: A number $a \not\equiv 0 \pmod p$ is a residue of degree $n$ modulo a prime number $p$ if and only if
 
+
$$
holds, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036430/e0364304.png" /> is the [[Legendre symbol|Legendre symbol]]. Thus, the Euler criterion gives a necessary and sufficient condition for a number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036430/e0364305.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036430/e0364306.png" />) to be a [[Quadratic residue|quadratic residue]] or non-residue modulo <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036430/e0364307.png" />. It was proved by L. Euler in 1761 (see [[#References|[1]]]).
+
a^{(p-1)/\delta} \equiv 1 \pmod p
 
+
$$
Euler also obtained a more general result: A number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036430/e0364308.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036430/e0364309.png" />) is a residue of degree <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036430/e03643010.png" /> modulo a prime number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036430/e03643011.png" /> if and only if
+
where $\delta = \mathrm{hcf}(p-1,n)$.
 
 
<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/e/e036/e036430/e03643012.png" /></td> </tr></table>
 
 
 
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036430/e03643013.png" />.
 
  
 
Both these assertions carry over easily to the case of a finite field.
 
Both these assertions carry over easily to the case of a finite field.
  
 
====References====
 
====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  L. Euler,  "Adnotationum ad calculum integralem Euleri"  G. Kowalewski (ed.) , ''Opera Omnia Ser. 1; opera mat.'' , '''12''' , Teubner  (1914)  pp. 493–538</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  I.M. Vinogradov,  "Elements of number theory" , Dover, reprint  (1954)  (Translated from Russian)</TD></TR></table>
+
<table>
 +
<TR><TD valign="top">[1]</TD> <TD valign="top">  L. Euler,  "Adnotationum ad calculum integralem Euleri"  G. Kowalewski (ed.) , ''Opera Omnia Ser. 1; opera mat.'' , '''12''' , Teubner  (1914)  pp. 493–538</TD></TR>
 +
<TR><TD valign="top">[2]</TD> <TD valign="top">  I.M. Vinogradov,  "Elements of number theory" , Dover, reprint  (1954)  (Translated from Russian)</TD></TR>
 +
</table>
  
  
Line 22: Line 26:
  
 
====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. Chapts. 5; 7; 8</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. Chapts. 5; 7; 8</TD></TR>
 +
</table>

Revision as of 22:25, 18 December 2014

If an integer $a$ is not divisible by a prime number $p>2$, then the congruence $$ a^{(p-1)/2} \equiv \left({\frac{a}{p}}\right) \pmod p $$ holds, where $\left({\frac{a}{p}}\right)$ is the Legendre symbol. Thus, the Euler criterion gives a necessary and sufficient condition for a number $a \not\equiv 0 \pmod p$ to be a quadratic residue or non-residue modulo $p$. It was proved by L. Euler in 1761 (see [1]).

Euler also obtained a more general result: A number $a \not\equiv 0 \pmod p$ is a residue of degree $n$ modulo a prime number $p$ if and only if $$ a^{(p-1)/\delta} \equiv 1 \pmod p $$ where $\delta = \mathrm{hcf}(p-1,n)$.

Both these assertions carry over easily to the case of a finite field.

References

[1] L. Euler, "Adnotationum ad calculum integralem Euleri" G. Kowalewski (ed.) , Opera Omnia Ser. 1; opera mat. , 12 , Teubner (1914) pp. 493–538
[2] I.M. Vinogradov, "Elements of number theory" , Dover, reprint (1954) (Translated from Russian)


Comments

References

[a1] G.H. Hardy, E.M. Wright, "An introduction to the theory of numbers" , Oxford Univ. Press (1979) pp. Chapts. 5; 7; 8
How to Cite This Entry:
Euler criterion. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Euler_criterion&oldid=35692
This article was adapted from an original article by S.A. Stepanov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article