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