Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
1  
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
1  
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
add comment

1 Answer

up vote 3 down vote accepted

If you know some field theory, you could use these two facts to prove the result.

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.

share|improve this answer
    
Thanks a lot @Fortuon Paendrag. –  Jozef May 5 '12 at 21:17
    
@Jozef Sure! Do let me know if you would like something explained in more detail. –  Ravi Donepudi May 5 '12 at 21:28
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.