Show that $\left( \frac{q}{p} \right) \equiv q^{(p-1) / 2} \mod p$, where $\left( \frac{q}{p} \right)$ is the Legendre Symbol 
Show that if $p$ is any odd prime then
$$\left( \frac{q}{p} \right) \equiv q^{\frac{p-1}{2}} \mod p.$$
stating any theory that you use. In particular, you may assume the existence of a primitive element in $G_p$.

Here $\left( \frac{q}{p} \right)$ is the Legendre Symbol and $G_p$ is the group of elements $g \mod p$ such that $\gcd(g,p) = 1$. I said that for some $a \in \mathbb{Z}$, we have
$$a \equiv q^{(p-1) / 2} \mod p \implies a^2 \equiv q^{(p-1)} \equiv 1 \mod p$$
by Fermat's little theorem. And so, by definition of the Legendre symbol, we have that if $q$ is a quadratic residue mod $p$ then $\left( \frac{q}{p} \right) \equiv q^{(p-1) / 2} \mod p$. I'm now stuck on how to show that it is $\equiv -1 $ if it isn't a quadratic residue. Obviously the hint with primitive elements comes into play somehow, but I can't see how it does.
Can someone help me please.
 A: Hint (assuming I have correctly guessed what the question really is):
Let $g$ be a primitive element. Find $a$ in such a way that $q\equiv g^a\pmod p$. Show that $x=q^{(p-1)/2}\equiv1$, iff $a$ is even. Show that $x^2\equiv1\pmod p$ irrespective of parity of $a$, so...
A: Let $g$ be a primitive root of $p$, a generator of the group of $p-1$ units. Suppose that $a$ is a QR. Then $a\equiv b^2\pmod{p}$ for some $b$. But $b$ is congruent to a power $g^e$ of $g$. So $a$ is congruent to $g^{2e}$. And by Fermat's Theorem, $(g^{2e})^{(p-1)/2}\equiv 1\pmod{p}$. 
Note that all $(p-1)/2$ numbers congruent to an even power of $g$ are automatically QR. 
Since there are $(p-1)/2$ QR, the numbers congruent to an odd power of $g$ are all NR. An odd power of $g$ cannot be congruent to $1$ modulo $p$. Let $x=a^{(p-1)/2}$. Then $x^2\equiv 1\pmod{p}$, so $x\equiv \pm 1\pmod{p}$. If $a$ is an NR, then $a^{(p-1)/2}\not\equiv 1 \pmod{p}$, so it is $\equiv -1\pmod{p}$. 
A: As you said, by Fermat's little theorem
$$
0 \equiv q^{p-1} - 1 = (q^{(p-1)/2} + 1)(q^{(p-1)/2} - 1) \pmod p.
$$
If $q$ is a quadratic residue, then $q^{(p-1)/2} \equiv 1 \pmod p$ again by Fermat, and if it is not, then $q^{(p-1)/2}+1$ must equals $0$ in $\mathbb{Z}_p$ since it is a field.
