1. An integer a is called a quadratic residue modulo n iff there exists some k ∈ Z such that k 2 ≡ a (mod n); it is called a quadratic nonresidue modulo n if there is no such k.

(a) Show that if a ≡ b (mod n) then a 2 (mod n) ≡ b 2 (mod n). Give a counterexample to show that the converse does not hold.

(b) Identify the congruence classes that are quadratic residues modulo 6. (Hint: using (a) we only need to look at the squares of the remainders modulo 6.)

(c) Identify the congruence classes that are quadratic residues modulo 7.

(d) Let p be an odd prime. Show that exactly half of the integers in the set {1, 2, . . . , p− 1} are quadratic residues.