0
$\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

2

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 the identity $\rm\ (c^k)^2\ \equiv\ c^{\:2\: k}\:.\ $ It easily generalizes from $\rm\ 2\to n\:.$

  • 0
    @Bill: Thanks for helping me out!2011-03-05
  • 0
    @Bill Dubuque: Thank you! How to show that if p is odd prime and g is a primitive root mod p, then index of g (mod p-1) = (p-1)/2 (mod p-1)2011-03-05
  • 1
    @Kira: Do you mean the index of $-1\:,\:$ i.e. $\rm\ I_g(-1)\ $?2011-03-05
  • 0
    @Bill Dubuque: This is the question: If p is an odd prime and g is a primitive root mod p, then I_g (p-1) = (p-1)/2 (mod p-1). Thank you for your help!2011-03-05
  • 1
    @Kira: That's better. Hint: $\rm\ x = g^{(p-1)/2}\ \Rightarrow\ x^2\equiv 1\:.\ $ But $\rm\ x\not\equiv 1\ \Rightarrow\ x \equiv\ \cdots$2011-03-05
  • 0
    @Bill Dubuque: Thanks for clarification!2011-03-06