One direction is pretty easy:

Now the other one: you'll need the following facts

i) All the quadratic residues modulo q are , and thus there are exactly

non-zero residues modulo q.

ii) The polynomial has at most different solutions in

iii) Since all the quadratic residues modulo q are roots of above, no

non-quadratic residue modulo q can be a root.

iv)... and Q.E.D.

Tonio