Suppose that n = p1p2 · · · pk is a product of k distinct odd primes. Let a be a

positive integer coprime to n. Show that the congruence x 2≡a (mod n) is solvable

if and only if each of the congruences x 2≡a (mod pi) is solvable.

x 2 means x squared