4.1 Legendre’s symbol
In the last chapter we discussed the linear congruence ax ≡ b (mod n). Here we shall study the quadratic congruence x2 ≡ a (mod n); in fact this amounts to the study of the general quadratic congruence ax2 + bx + c ≡ 0 (mod n), since on writing d = b2 − 4ac and y = 2ax + b, the latter gives y2 ≡ d (mod 4an).
Let a be any integer, let n be a natural number and suppose that (a, n) = 1. Then a is called a quadratic residue (mod n) if the congruence x2 ≡ a (mod n) is soluble; otherwise it is called a quadratic non-residue (mod n). The Legendre symbol (), where p is a prime and (a, p) = 1 is defined as 1 if ...