# Legendre symbol

The Legendre symbol is a shorthand notation used in number theory , a branch of mathematics . It is named after the French mathematician Adrien-Marie Legendre .

## Definition and notation

The Legendre symbol indicates whether the number is a quadratic remainder modulo or a quadratic non- remainder modulo . It must be an integer and a prime number . ${\ displaystyle a}$ ${\ displaystyle p}$${\ displaystyle p}$${\ displaystyle a}$${\ displaystyle p}$

The following applies:

${\ displaystyle \ left ({\ frac {a} {p}} \ right) = {\ begin {cases} 1 & {\ mbox {if}} a {\ mbox {quadratic remainder modulo}} p {\ mbox {is }} \\ - 1 & {\ mbox {if}} a {\ mbox {quadratic non-remainder modulo}} p {\ mbox {is}} \\ 0 & {\ mbox {if}} a {\ mbox {a multiple of} } p {\ mbox {ist}} \ end {cases}}}$

The Legendre symbol is a special case of the Jacobi symbol that has the same spelling. Further notation variants for the Legendre symbol are and . ${\ displaystyle (a / p)}$${\ displaystyle L (a, p)}$

## calculation

The Euler's criterion indicates how the Legendre symbol for itself odd prime number calculate can: ${\ displaystyle p}$

${\ displaystyle \ left ({\ frac {a} {p}} \ right) \ equiv a ^ {\ frac {p-1} {2}} {\ pmod {p}}}$.

The following applies to the only even prime number : ${\ displaystyle 2}$

${\ displaystyle -1 \ equiv 1 {\ pmod {2}}}$.

Every odd number is a quadratic remainder and every even number is a multiple of 2, so modulo 2 there are no non-residues:

${\ displaystyle \ left ({\ frac {a} {2}} \ right) = a {\ bmod {2}}}$.

Zolotareff's lemma provides another calculation option , according to that for odd prime numbers

${\ displaystyle \ left ({\ frac {a} {p}} \ right) = \ operatorname {sgn} (\ pi _ {a, p})}$

applies, where that through ${\ displaystyle \ pi _ {a, p}}$

${\ displaystyle \ pi _ {a, p} (k) \ equiv a \ cdot k {\ pmod {p}}}$

defined permutation of the numbers of , and denotes the sign of a permutation. ${\ displaystyle k = 0, \ dotsc p-1}$${\ displaystyle \ operatorname {sgn}}$

## Examples

2 is a quadratic remainder modulo 7 - in fact, yes : ${\ displaystyle 2 \ equiv 3 ^ {2} {\ pmod {7}}}$

${\ displaystyle \ left ({\ frac {2} {7}} \ right) \ equiv 2 ^ {\ frac {7-1} {2}} = 2 ^ {3} \ equiv 1 \ mod 7}$

5 is a quadratic non-remainder modulo 7:

${\ displaystyle \ left ({\ frac {5} {7}} \ right) \ equiv 5 ^ {\ frac {7-1} {2}} = 5 ^ {3} \ equiv 6 \ equiv -1 \ mod 7}$

14 is divisible by 7 (i.e. neither remainder nor non-remainder of 7):

${\ displaystyle \ left ({\ frac {14} {7}} \ right) \ equiv 14 ^ {\ frac {7-1} {2}} = 14 ^ {3} \ equiv 0 \ mod 7}$

## Calculation rules

The quadratic reciprocity law makes important statements about calculating with the Legendre symbol.

In addition, apply to all whole numbers , all prime numbers and the following calculation rules: ${\ displaystyle a}$${\ displaystyle b}$${\ displaystyle p}$

• ${\ displaystyle a \ equiv b {\ pmod {p}} \ Rightarrow \ left ({\ frac {a} {p}} \ right) = \ left ({\ frac {b} {p}} \ right)}$
• ${\ displaystyle \ left ({\ frac {a} {p}} \ right) \ cdot \ left ({\ frac {b} {p}} \ right) = \ left ({\ frac {a \ cdot b} {p}} \ right)}$
• ${\ displaystyle \ sum _ {k = 1} ^ {p-1} \ left ({\ frac {k} {p}} \ right) = 0}$for .${\ displaystyle p \ neq 2}$

## Special values

The following applies to all odd prime numbers${\ displaystyle p}$

${\ displaystyle \ left ({\ frac {1} {p}} \ right) = 1}$
${\ displaystyle \ left ({\ frac {2} {p}} \ right) = (- 1) ^ {\ frac {p ^ {2} -1} {8}} = {\ begin {cases} 1 & { \ mbox {for}} p \ equiv 1 {\ mbox {or}} 7 {\ pmod {8}} \\ - 1 & {\ mbox {for}} p \ equiv 3 {\ mbox {or}} 5 {\ pmod {8}}. \ end {cases}}}$
${\ displaystyle \ left ({\ frac {-1} {p}} \ right) = (- 1) ^ {\ frac {p-1} {2}} = {\ begin {cases} 1 & {\ mbox { for}} p \ equiv 1 {\ pmod {4}} \\ - 1 & {\ mbox {for}} p \ equiv 3 {\ pmod {4}}. \ end {cases}}}$

These special values ​​are sufficient to calculate each non-vanishing Legendre symbol by repeatedly dividing the "numerator" into prime factors, applying the quadratic reciprocity law and modulo reduction. So is for example

${\ displaystyle \ left ({\ frac {10} {31}} \ right) = \ left ({\ frac {2} {31}} \ right) \ left ({\ frac {5} {31}} \ right) = 1 \ cdot (-1) ^ {{\ frac {5-1} {2}} {\ frac {31-1} {2}}} \ left ({\ frac {31} {5}} \ right) = \ left ({\ frac {1} {5}} \ right) = 1}$

## The special position of the number 3

With integer division, the number 3 returns the values ​​0, 1 and −1 as modulo. This corresponds exactly to the values ​​of the Legendre symbol. The following applies:

${\ displaystyle \ left ({\ frac {a} {3}} \ right) \ equiv a ^ {\ frac {3-1} {2}} \ \ operatorname {mod} \ 3 = a \ \ operatorname {mod } \ 3}$

On the other hand, the following also applies:

${\ displaystyle \ left ({\ frac {3} {p}} \ right) = \ prod _ {l = 1} ^ {\ frac {p-1} {2}} \ left [3-4 \, \ sin ^ {2} {\ left ({\ frac {2 \ pi l} {p}} \ right)} \ right]}$

## Special features of prime numbers

See under Pythagorean prime number .