7. Quadratic nonresidues modulo n The set Q, of quadratic residues modulo n con-

sists of those [a], ∈ Z for which we can solve x² = a mod n for some x with [x], ∈

Z

(a) Let p be an odd prime and g a primitive root for Z

(i) Show that [a], is a quadratic residue modulo p if and only if

$$a = g^{2i} mod p$$

for some i ∈ N.

(ii) Conclude that Q, has exactly (p-1)/2 many elements.

(iii) Show: If a ∈ Qp, then there are exactly two elements in {0, 1, ..., p - 1)
that solve x² = a mod p.

(b) Compute the set Q₃₁.

(c) Let n = p · q for odd prime numbers p and q. Show that [a]_n ∈ Q_n if and only if [a]_p ∈ Q_p and [a]_q ∈ Q_q.