Legendre symbol

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^2 = a mod p) -1 if a is not a square modulo p.

Furthermore, if a is devisible 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).