0
$\begingroup$

Here is the setup:

Suppose $p$ is an odd prime.

A primitive root modulo $p$ is an integer with order $p-1$.

Suppose further $\omega$ is a primitive root modulo $p$.

It can be shown that $$\left(\frac{\omega}{p}\right)=-1$$

Here is the question:

Using primitive roots show there are the same number of quadratic residues as there are quadratic nonresidues modulo $p$.

My thoughts:

Any primitive root is a quadratic nonresidue by above.

For any primitive root we have $$\left(\frac{\omega}{p}\right)=-1$$ so by Euler's criterion we get $$\left(\frac{\omega}{p}\right)=-1 \equiv \omega^{(p-1)/2} \mod p$$

By Lagrange's theorem (for polynomials) we have the equation $$-1 \equiv \omega^{(p-1)/2} \mod p$$ has at most $(p-1)/2$ distinct solutions modulo $p$.

Here are just some things that spring to mind (I don't know if they are along the right tracks)

any help?

$\endgroup$
5
  • $\begingroup$ There are $\frac {p-1}2$ squares...For every element $x^2\equiv (-x)^2 \pmod p$ and, since it's a field, there can't be any other square roots. Hence there are also $\frac {p-1}2$ non squares. $\endgroup$ – lulu Jan 12 '17 at 18:50
  • $\begingroup$ I don't understand how do you know that there are $(p-1)/2$ quadratic residues. It just seems like you state what I need to prove. I also need to use primitive roots in my answer. $\endgroup$ – Ryan S Jan 12 '17 at 18:52
  • $\begingroup$ I gave a proof! Group the residues as $\{\pm 1, \pm 2, \cdots, \pm \frac {p-1}2\}$. Squaring each term in that gives you all of the squares. $\endgroup$ – lulu Jan 12 '17 at 18:53
  • $\begingroup$ Yeah I get that proof but how does that use primitive roots? It says specifically that primitive roots must be used. $\endgroup$ – Ryan S Jan 12 '17 at 18:55
  • $\begingroup$ Ok, show that the squares are $g^{2i}$ and the non-squares are $g^{2i-1}$. $\endgroup$ – lulu Jan 12 '17 at 18:57
0
$\begingroup$

An idea: take all the odd integers between $\;1\;$ and $\;p-1\;$, whose number is precisely $\;\cfrac{p-1}2\;$, and now observe that, for $\;n\in\Bbb N\;$ :

$$\left(\frac wp\right)=w^{(p-1)/2}\implies \left(\frac{w^{\frac{2n-1}2}}p\right)=\left(w^{\frac{2n-1}2}\right)^{\frac{p-1}2}=\left(w^{\frac{(p-1)}2}\right)^{\frac{2n-1}2}=(-1)^{\frac{2n-1}2}=-1$$

$\endgroup$
2
  • $\begingroup$ What is $n$ here? $\endgroup$ – Ryan S Jan 12 '17 at 18:58
  • $\begingroup$ @RyanS A natural number. $\endgroup$ – DonAntonio Jan 12 '17 at 18:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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