I'd love your help with the following problem:
Let $p$ be an odd prime. I need to show that for any $a$ prime to $p$, either $a^{\frac{(p-1)}{2}}\equiv 1\pmod p$ or $a^{\frac{(p-1)}{2}}\equiv -1\pmod p$.
I want to use the theorem about n-power residues: if there's a primitive root for $p$ and $\gcd (a,m)=1$ so $a$ is $n$-power residue $\iff$ $a^{\frac {\phi(p)}{d}}\equiv 1\pmod p$ where $d= \gcd (n, \phi(p))$, I'm just not sure how am I suppose to use it.
I have this odd prime $p$, it certainly have a primitive root and $\gcd (a,m)=1$ so do I choose $n=2$ and say that since I know that $2= \gcd (n, \phi(p))$ so $a^{\frac {\phi(p)}{2}}\equiv 1\pmod p$ or $a^{\frac {p-1}{2}}\equiv 1\pmod p$? what exactly does it mean and how should I use that to conclude what I need?
Thanks a lot!