# $n$-power residues theorem and its use

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!

-
If $x=a^{(p-1)/2}$ can you compute the residue class of $x^2$ modulo $p$? What does that say about the residue class of $x$? –  Jyrki Lahtonen May 5 '12 at 20:46
But do you really want to use the $n$-power residue theorem? To use it you would need to assume that $a$ is a quadratic residue, and you are not given that?! Also, your goal is to show that something is congruent to $\pm1$. The $n$-power residue theorem only gives you $+1$?! –  Jyrki Lahtonen May 5 '12 at 20:52
I don't have to use it, it's just pop to my head since it's look like something that might be helpful. I'm into the easiest and most understandable way. –  Jozef May 5 '12 at 20:54
If you're unsure about how quadratic residues work, then trying to figure it out using n-th power residues is overkill. Definitely far from the easiest way. How did you even find out about this criterion for n-th power residues? Come back to earth and simply read in books about quadratic residues. The equivalence you're asking about is in almost any number theory book. –  KCd May 5 '12 at 22:07

i) If $p$ is a prime,$\mathbb{Z}_p$ (The integers modulo $p$) is a field.
ii) If its coefficients are in a field,any polynomial of degree $n$ has at most $n$ roots.
So, the polynomial $x^2-1$ has two roots: $1,-1$ in $\mathbb{Z}_p$.(Both distinct since $p>2$.) So, if $a^{\frac{p-1}{2}}$ was neither $1$ or $-1$, $a^{\phi(p)}=a^{p-1} =(a^{\frac{p-1}{2}})^2 \neq 1$, which we certainly know must be the case.