Let be an odd prime and the set of all quadratic residues

Lemma 1:

Proof:

We have But note that Hence we can write since This shows that there are at most distinct quadratic residues But now suppose that and Then or The latter would imply that which is impossible for Hence if This proves that there are exactly quadratic residues