Generators of the cyclic group ${\mathbb{Z}_p^*}$

Question

Given two prime numbers ${p, q > 2}$, where ${p=2q+1}$, I have to show that the cyclic group ${G = \mathbb{Z}_p^*}$ has ${p-1}$ generators.

I know that ${|G| = p-1 = 2q}$ and that ${a \in G}$ is a generator iff ${a^2 \neq 1~\text{mod}~p}$ and ${a^q \neq 1~\text{mod}~p}$. So there have to be ${2q}$ solutions for these two equations, but I have no idea how to show that.

Can you give me a hint?

Answer 1

How many generators does a cyclic group of order $n$ have? What is the order of $({\bf Z}/p{\bf Z})^\times$?