Legendre symbol

The Legendre symbol is used by mathematicians in the theory of numbers, particularly in the fields of factorization? and [quadratic residues]?.

If p is a prime number and a is an integer relatively prime to p, then we define the Legendre? symbol (a/p) to be:

1 if a is a square modulo p (that is to say there exists an integer x such that x² = a mod p)

-1 if a is not a square modulo p.

Furthermore, if a is divisible by p we say (a/p) = 0.

Euler proved that (a/p) = a^((p-1)/2) mod p. Thus we can see that the Legendre symbol is multiplicative, i.e. (ab/p) = (a/p)(b/p).