1
$\begingroup$

I have a problem in solving my number theory homework. My question is as follows:

Let $p$ be an odd prime. Prove that $a$ is a quadratic residue mod $p$ if and only if the $I_{g}(x)$ (index with respect to any primitive root of $p$) is even.

Please edit my writing. Thanks. Does anyone know where to start? Thank you very much for everything!

1 Answers 1

4

Hint $\ $ Let $\rm\:c\:$ be a primitive root. If $\rm\ a \equiv b^2\: $ and $\rm\ b \equiv c^k\ $ then $\rm\ a \equiv (\cdots)^2\ $ so $\rm\:a\:$ has even index. Conversely suppose $\rm\:a\:$ has even index $\rm\ I_c(a) = 2\ k\:.\:$ Then $\rm\ a \equiv (\cdots)^2\ $ so $\rm\:a\:$ is a quadratic residue.

Essentially the proof boils down to $\rm\ (c^k)^2 \equiv c^{2 k}\,$ and $\rm\,2k\,$ stays even when reduced mod $\,\rm 2m = p\!-\!1.\,$ It easily generalizes from $\rm\ 2\to n\,$ when $\,\rm n\mid p-1.$

  • 0
    @Bill Dubuque: Thanks for clarification!2011-03-06