1
$\begingroup$

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!

  • 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$?2012-05-05
  • 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$?!2012-05-05
  • 0
    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.2012-05-05
  • 0
    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.2012-05-05

1 Answers 1

3

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.

  • 0
    Thanks a lot @Fortuon Paendrag.2012-05-05
  • 0
    @Jozef Sure! Do let me know if you would like something explained in more detail.2012-05-05