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{wenn }}a{\mbox{ quadratischer Rest modulo }}p{\mbox{ ist}}\\-1&{\mbox{wenn }}a{\mbox{ quadratischer Nichtrest modulo }}p{\mbox{ ist}}\\0&{\mbox{wenn }}a{\mbox{ ein Vielfaches von }}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{ für }}p\equiv 1{\mbox{ oder }}7{\pmod {8}}\\-1&{\mbox{ für }}p\equiv 3{\mbox{ oder }}5{\pmod {8}}.\end{cases}}}$

${\displaystyle \left({\frac {-1}{p}}\right)=(-1)^{\frac {p-1}{2}}={\begin{cases}1&{\mbox{ für }}p\equiv 1{\pmod {4}}\\-1&{\mbox{ für }}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 .