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!

  • 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
    @Jozef Sure! Do let me know if you would like something explained in more detail.2012-05-05