Legendre symbol

The Legendre symbol is used ... by mathematicians in attempts to woo women. (If this is not right, please correct it.)

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 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).