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

Legendre symbol

From Prime-Wiki
Revision as of 10:39, 6 February 2019 by Karbon (talk | contribs)
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 p is an odd prime number and a is an integer, then the Legendre symbol

[math]\displaystyle{ \left(\frac{a}{p}\right) }[/math]

is:

  • 0 if p divides a;
  • 1 if a is a square modulo p — that is to say there exists an integer k such that k2a (mod p), or in other words a is a quadratic residue modulo p;
  • −1 if a is not a square modulo p, or in other words a is not a quadratic residue modulo p.

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 ab (mod p), 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} }[/math], i.e. = 1 if p ≡ 1 (mod 4) and = −1 if p ≡ 3 (mod 4)
  5. [math]\displaystyle{ \left(\frac{2}{p}\right) = (-1)^{(p^2-1)/8} }[/math], i.e. = 1 if p ≡ 1 or 7 (mod 8) and = −1 if p ≡ 3 or 5 (mod 8)
  6. If q 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