The idea is that are a complete set of residues mod p when is a primitive root.

So you can write for some integer , given any nonzero a.

You might want to show that , the 1 and the -1 holding respectively if is a square or not.

To do this, assume is a power of some primitive root and see where you can take it from there.