Difference between revisions of "Legendre symbol"
From Encyclopedia of Mathematics
(Importing text file) |
(LaTeX) |
||
| Line 1: | Line 1: | ||
| − | An [[ | + | An [[arithmetic function]] of the numbers $a$ and $p$, defined for odd prime numbers $p$ and integers $a$ not divisible by $p$. The Legendre symbol is denoted by $\left({\frac{a}{p}}\right)$. The Legendre symbol $\left({\frac{a}{p}}\right) = +1$ if the [[congruence]] $x^2 \equiv a \pmod p$ is solvable; otherwise, $\left({\frac{a}{p}}\right) = -1$. The Legendre symbol is sometimes defined for numbers $a$ divisible by $p$ by putting $\left({\frac{a}{p}}\right) = 0$ in this case. The Legendre symbol has the following properties: |
| − | 1) if | + | 1) if $a \equiv b \pmod p$, then $\left({\frac{a}{p}}\right) = \left({\frac{b}{p}}\right)$; |
| − | 2) | + | 2) $\left({\frac{1}{p}}\right) = 1$; |
| − | 3) | + | 3) $\left({\frac{a}{p}}\right) \equiv a^{(p-1)/2} \pmod p$; |
| − | 4) | + | 4) $\left({\frac{ab}{p}}\right) = \left({\frac{a}{p}}\right) \left({\frac{b}{p}}\right)$; |
| − | 5) | + | 5) $\left({\frac{-1}{p}}\right) = (-1)^{(p-1)/2}$; |
| − | 6) | + | 6) $\left({\frac{2}{p}}\right) = (-1)^{(p^2-1)/8}$; |
| − | 7) if | + | 7) if $p$ and $q$ are odd prime numbers, then |
| + | $$ | ||
| + | \left({\frac{p}{q}}\right) = \left({\frac{q}{p}}\right) (-1)^{(p-1)/2 \cdot (q-1)/2} \ . | ||
| + | $$ | ||
| − | + | The last fact, first proved by C.F. Gauss (1796), is called the [[quadratic reciprocity law]]. The above properties make it possible to calculate the Legendre symbol easily, without resorting to solving congruences. For example, | |
| + | $$ | ||
| + | \left({\frac{438}{593}}\right) = \left({\frac{2}{593}}\right)\left({\frac{3}{593}}\right)\left({\frac{73}{593}}\right) = (+1)\left({\frac{593}{3}}\right)\left({\frac{593}{73}}\right) = \left({\frac{2}{3}}\right)\left({\frac{9}{73}}\right) = (-1)(+1) = -1 | ||
| + | $$ | ||
| − | + | The calculation of the Legendre symbol is facilitated still more by the use of the [[Jacobi symbol]]. For fixed $p$ the Legendre symbol is a real character of the multiplicative group of residue classes modulo $p$ (cf. [[Character of a group|Character of a group]]). | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | The calculation of the Legendre symbol is facilitated still more by the use of the [[ | ||
It was introduced by A.M. Legendre in 1785. | It was introduced by A.M. Legendre in 1785. | ||
Latest revision as of 18:03, 19 December 2014
An arithmetic function of the numbers $a$ and $p$, defined for odd prime numbers $p$ and integers $a$ not divisible by $p$. The Legendre symbol is denoted by $\left({\frac{a}{p}}\right)$. The Legendre symbol $\left({\frac{a}{p}}\right) = +1$ if the congruence $x^2 \equiv a \pmod p$ is solvable; otherwise, $\left({\frac{a}{p}}\right) = -1$. The Legendre symbol is sometimes defined for numbers $a$ divisible by $p$ by putting $\left({\frac{a}{p}}\right) = 0$ in this case. The Legendre symbol has the following properties:
1) if $a \equiv b \pmod p$, then $\left({\frac{a}{p}}\right) = \left({\frac{b}{p}}\right)$;
2) $\left({\frac{1}{p}}\right) = 1$;
3) $\left({\frac{a}{p}}\right) \equiv a^{(p-1)/2} \pmod p$;
4) $\left({\frac{ab}{p}}\right) = \left({\frac{a}{p}}\right) \left({\frac{b}{p}}\right)$;
5) $\left({\frac{-1}{p}}\right) = (-1)^{(p-1)/2}$;
6) $\left({\frac{2}{p}}\right) = (-1)^{(p^2-1)/8}$;
7) if $p$ and $q$ are odd prime numbers, then $$ \left({\frac{p}{q}}\right) = \left({\frac{q}{p}}\right) (-1)^{(p-1)/2 \cdot (q-1)/2} \ . $$
The last fact, first proved by C.F. Gauss (1796), is called the quadratic reciprocity law. The above properties make it possible to calculate the Legendre symbol easily, without resorting to solving congruences. For example, $$ \left({\frac{438}{593}}\right) = \left({\frac{2}{593}}\right)\left({\frac{3}{593}}\right)\left({\frac{73}{593}}\right) = (+1)\left({\frac{593}{3}}\right)\left({\frac{593}{73}}\right) = \left({\frac{2}{3}}\right)\left({\frac{9}{73}}\right) = (-1)(+1) = -1 $$
The calculation of the Legendre symbol is facilitated still more by the use of the Jacobi symbol. For fixed $p$ the Legendre symbol is a real character of the multiplicative group of residue classes modulo $p$ (cf. Character of a group).
It was introduced by A.M. Legendre in 1785.
References
| [1] | 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) |
How to Cite This Entry:
Legendre symbol. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Legendre_symbol&oldid=14735
Legendre symbol. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Legendre_symbol&oldid=14735
This article was adapted from an original article by Yu.V. Nesterenko (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article