Note: Due to changes in the Riesel prime template, most of those pages (and related) are not shown properly.
This will take some time!
Wanna help? Please move any Riesel prime page first, then edit/add the base parameter.
Navigation
Topics Register • News • History • How to • Sequences statistics • Template prototypes

Legendre symbol

From Prime-Wiki
Revision as of 20:30, 26 October 2020 by Happy5214 (talk | contribs) (Improving formulas)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

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