| Currently there may be errors shown on top of a page, because of a missing Wiki update (PHP version and extension DPL3). |
Navigation
| Topics | Help • Register • News • History • How to • Sequences statistics • Template prototypes |
Difference between revisions of "Legendre symbol"
m |
(Moving to functions category) |
||
| (One intermediate revision by the same user not shown) | |||
| Line 2: | Line 2: | ||
==Definition== | ==Definition== | ||
| − | If | + | If <math>p</math> is an odd [[prime]] number and <math>a</math> is an [[integer]], then the Legendre symbol |
:<math>\left(\frac{a}{p}\right)</math> | :<math>\left(\frac{a}{p}\right)</math> | ||
is: | is: | ||
| − | *0 if | + | *0 if <math>p</math> divides <math>a</math>; |
| − | *1 if | + | *1 if <math>a</math> is a square [[modular arithmetic|modulo]] <math>p</math> — that is to say there exists an integer <math>k</math> such that <math>k^2 \equiv a \pmod{p}</math>, or in other words <math>a</math> is a quadratic residue modulo <math>p</math>; |
| − | *−1 if | + | *−1 if <math>a</math> is not a square modulo <math>p</math>, or in other words <math>a</math> is not a quadratic residue modulo <math>p</math>. |
==Properties of the Legendre symbol== | ==Properties of the Legendre symbol== | ||
There are a number of useful properties of the Legendre symbol which can be used to speed up calculations. They include: | There are a number of useful properties of the Legendre symbol which can be used to speed up calculations. They include: | ||
#<math>\left(\frac{ab}{p}\right) = \left(\frac{a}{p}\right)\left(\frac{b}{p}\right)</math> (it is a completely multiplicative function in its top argument) | #<math>\left(\frac{ab}{p}\right) = \left(\frac{a}{p}\right)\left(\frac{b}{p}\right)</math> (it is a completely multiplicative function in its top argument) | ||
| − | #If | + | #If <math>a \equiv b \pmod{p}</math>, then <math>\left(\frac{a}{p}\right) = \left(\frac{b}{p}\right)</math> |
#<math>\left(\frac{1}{p}\right) = 1</math> | #<math>\left(\frac{1}{p}\right) = 1</math> | ||
| − | #<math>\left(\frac{-1}{p}\right) = (-1)^{(p-1)/2} | + | #<math>\left(\frac{-1}{p}\right) = (-1)^{(p-1)/2} = \begin{cases} 1 & \text{if } p \equiv 1 \pmod{4} \\ -1 & \text{if } p \equiv 3 \pmod{4} \end{cases}</math> |
| − | #<math>\left(\frac{2}{p}\right) = (-1)^{(p^2-1)/8} | + | #<math>\left(\frac{2}{p}\right) = (-1)^{(p^2-1)/8} = \begin{cases} 1 & \text{if } p \equiv 1 \text { or } 7 \pmod{8} \\ -1 & \text{if } p \equiv 3 \text{ or } 5 \pmod{8} \end{cases}</math> |
| − | #If | + | #If <math>q</math> is an odd prime then <math>\left(\frac{q}{p}\right) = \left(\frac{p}{q}\right)(-1)^{ ((p-1)/2) ((q-1)/2) }</math> |
The last property is known as the [[law of quadratic reciprocity]]. The properties 4 and 5 are traditionally known as the ''supplements'' to quadratic reciprocity. | The last property is known as the [[law of quadratic reciprocity]]. The properties 4 and 5 are traditionally known as the ''supplements'' to quadratic reciprocity. | ||
The Legendre symbol is related to Euler's criterion and [[Leonhard Euler|Euler]] proved that | The Legendre symbol is related to Euler's criterion and [[Leonhard Euler|Euler]] proved that | ||
| − | :<math>\left(\frac{a}{p}\right) \equiv a^{(p-1)/2} | + | :<math>\left(\frac{a}{p}\right) \equiv a^{(p-1)/2} \pmod{p}</math> |
==External links== | ==External links== | ||
*[[Wikipedia:Legendre_symbol|Wikipedia]] | *[[Wikipedia:Legendre_symbol|Wikipedia]] | ||
| − | [[Category: | + | |
| + | [[Category:Functions]] | ||
Latest revision as of 18:57, 28 September 2023
The Legendre symbol, named after the French mathematician Adrien-Marie Legendre, is used in connection with factorization and quadratic residues.
Definition
If [math]\displaystyle{ p }[/math] is an odd prime number and [math]\displaystyle{ a }[/math] is an integer, then the Legendre symbol
- [math]\displaystyle{ \left(\frac{a}{p}\right) }[/math]
is:
- 0 if [math]\displaystyle{ p }[/math] divides [math]\displaystyle{ a }[/math];
- 1 if [math]\displaystyle{ a }[/math] is a square modulo [math]\displaystyle{ p }[/math] — that is to say there exists an integer [math]\displaystyle{ k }[/math] such that [math]\displaystyle{ k^2 \equiv a \pmod{p} }[/math], or in other words [math]\displaystyle{ a }[/math] is a quadratic residue modulo [math]\displaystyle{ p }[/math];
- −1 if [math]\displaystyle{ a }[/math] is not a square modulo [math]\displaystyle{ p }[/math], or in other words [math]\displaystyle{ a }[/math] is not a quadratic residue modulo [math]\displaystyle{ p }[/math].
Properties of the Legendre symbol
There are a number of useful properties of the Legendre symbol which can be used to speed up calculations. They include:
- [math]\displaystyle{ \left(\frac{ab}{p}\right) = \left(\frac{a}{p}\right)\left(\frac{b}{p}\right) }[/math] (it is a completely multiplicative function in its top argument)
- If [math]\displaystyle{ a \equiv b \pmod{p} }[/math], then [math]\displaystyle{ \left(\frac{a}{p}\right) = \left(\frac{b}{p}\right) }[/math]
- [math]\displaystyle{ \left(\frac{1}{p}\right) = 1 }[/math]
- [math]\displaystyle{ \left(\frac{-1}{p}\right) = (-1)^{(p-1)/2} = \begin{cases} 1 & \text{if } p \equiv 1 \pmod{4} \\ -1 & \text{if } p \equiv 3 \pmod{4} \end{cases} }[/math]
- [math]\displaystyle{ \left(\frac{2}{p}\right) = (-1)^{(p^2-1)/8} = \begin{cases} 1 & \text{if } p \equiv 1 \text { or } 7 \pmod{8} \\ -1 & \text{if } p \equiv 3 \text{ or } 5 \pmod{8} \end{cases} }[/math]
- If [math]\displaystyle{ q }[/math] is an odd prime then [math]\displaystyle{ \left(\frac{q}{p}\right) = \left(\frac{p}{q}\right)(-1)^{ ((p-1)/2) ((q-1)/2) } }[/math]
The last property is known as the law of quadratic reciprocity. The properties 4 and 5 are traditionally known as the supplements to quadratic reciprocity.
The Legendre symbol is related to Euler's criterion and Euler proved that
- [math]\displaystyle{ \left(\frac{a}{p}\right) \equiv a^{(p-1)/2} \pmod{p} }[/math]
