Legendre symbol

from Wikipedia, the free encyclopedia

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 .

The following applies:

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 .


The Euler's criterion indicates how the Legendre symbol for itself odd prime number calculate can:


The following applies to the only even prime number :


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


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

applies, where that through

defined permutation of the numbers of , and denotes the sign of a permutation.


2 is a quadratic remainder modulo 7 - in fact, yes :

5 is a quadratic non-remainder modulo 7:

14 is divisible by 7 (i.e. neither remainder nor non-remainder of 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:

  • for .

Special values

The following applies to all odd prime numbers

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

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:

On the other hand, the following also applies:

Special features of prime numbers

See under Pythagorean prime number .