Difference between revisions of "Euler criterion"
From Encyclopedia of Mathematics
(LaTeX) |
m (link) |
||
| Line 6: | Line 6: | ||
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]]]). | 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]]]). | ||
| − | 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 | + | Euler also obtained a more general result: A number $a \not\equiv 0 \pmod p$ is a [[power residue]] of degree $n$ modulo a prime number $p$ if and only if |
$$ | $$ | ||
a^{(p-1)/\delta} \equiv 1 \pmod p | a^{(p-1)/\delta} \equiv 1 \pmod p | ||
Latest revision as of 07:30, 19 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 power 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=35693
Euler criterion. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Euler_criterion&oldid=35693
This article was adapted from an original article by S.A. Stepanov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article