Navigation
Topics Register • News • History • How to • Sequences statistics • Template prototypes

Difference between revisions of "Legendre symbol"

From Prime-Wiki
Jump to: navigation, search
m
(Improving formulas)
 
Line 2: Line 2:
  
 
==Definition==
 
==Definition==
If ''p'' is an odd [[prime]] number and ''a'' is an [[integer]], then the Legendre symbol
+
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 ''p'' divides ''a'';
+
*0 if <math>p</math> divides <math>a</math>;
*1 if ''a'' is a square [[modular arithmetic|modulo]] ''p'' &mdash; that is to say there exists an integer ''k'' such that ''k''<sup>2</sup> &equiv; ''a'' (mod ''p''), or in other words ''a'' is a quadratic residue modulo ''p'';
+
*1 if <math>a</math> is a square [[modular arithmetic|modulo]] <math>p</math> &mdash; 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>;
*&minus;1 if ''a'' is not a square modulo ''p'', or in other words ''a'' is not a quadratic residue modulo ''p''.
+
*&minus;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 ''a'' &equiv; ''b'' (mod ''p''), then <math>\left(\frac{a}{p}\right) = \left(\frac{b}{p}\right)</math>
+
#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>, i.e. = 1 if ''p'' &equiv; 1 (mod 4) and = &minus;1 if ''p'' &equiv; 3 (mod 4)
+
#<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>, i.e.  = 1 if ''p'' &equiv; 1 or 7 (mod 8) and  = &minus;1 if ''p'' &equiv; 3 or 5 (mod 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 ''q'' is an odd prime then <math>\left(\frac{q}{p}\right) = \left(\frac{p}{q}\right)(-1)^{ ((p-1)/2) ((q-1)/2) }</math>
+
#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}\,\pmod p</math>
+
:<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:Math]]
 
[[Category:Math]]

Latest revision as of 20:30, 26 October 2020

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:

  1. [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)
  2. If [math]\displaystyle{ a \equiv b \pmod{p} }[/math], then [math]\displaystyle{ \left(\frac{a}{p}\right) = \left(\frac{b}{p}\right) }[/math]
  3. [math]\displaystyle{ \left(\frac{1}{p}\right) = 1 }[/math]
  4. [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]
  5. [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]
  6. 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]

External links