Legendre-Symbol

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

These three notations respectively indicate whether the number is a quadratic residue modulo p or quadratic non- residue modulo p. Here is a prime number must be. It is

The Legendre symbol is a special case of the Jacobi symbol has the same notation.

The Euler's criterion indicates, how the Legendre symbol can be calculated for all primes except 2:

The number 2 is ignored by the formula, As is true

That is, all numbers are either multiples of 2 or quadratic residues modulo 2.

Examples

Calculation rules

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

There are now and a prime number. Then, following processing rules apply:

• Unless.

The special position of number 3

The number 3 provides for the integer division as modulo the values ​​0, 1 and -1. This corresponds exactly to the values ​​of the Legendre symbol. Thus:

So if you can decompose a Legendre symbol in Legendre symbols of the form, so can the value that the Legendre symbol returns, calculated easily.

On the other hand, the following applies:

• Number Theory