The congruence x2 ≡ a (mod p), where p is an odd prime and a is any number not divisible by p, sometimes has a solution, but sometimes it has not. Gauss’s symbol (a/p), also known as Legendre’s symbol, is defined as (a/p) = l if there exists at least one x as a solution to this congruence and (a/p) = − l if no such solution exists.
The “Law of Reciprocity”, the famous theorem by Gauss, then states that, if p and q are odd primes,
![](//static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20180918030426497-0511:S002555720005213X:S002555720005213X_inline001.gif?pub-status=live)
where ![](//static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20180918030426497-0511:S002555720005213X:S002555720005213X_inline002.gif?pub-status=live)