2
$\begingroup$

I am given the fact that the Legendre symbol, $\left(\frac{\omega}{p}\right) = -1$. How can I use this to prove that there are as many quadratic residues as quadratic non residues modulo p? Here, $p$ is prime and $\omega$ is a primitive root modulo $p$.

$\endgroup$
3
$\begingroup$

Hint : The group of the units of $\mathbb Z_p$ consists of the elements $\omega,\omega^2,\omega^3,...,\omega^{p-1}=e$ because $\omega$ has order $p-1$ and $w^k$ for $k\ge 1$ is a quadratic residue modulo $p$ if and only if $k$ is even.

Now you only have to consider that $p-1$ is even because $p=2$ does not allow $\left(\frac{\omega}{p}\right)=-1$

$\endgroup$
1
  • $\begingroup$ I think my problem is that I am unsure as to whether I am allowed to simply state that $\omega^k$ is a quadratic residue modulo p iff $k$ is even or if I have to prove it (I know how to prove that it is true) :/ $\endgroup$ – Ineedhelppls Jan 29 '16 at 13:37
1
$\begingroup$

You don't need $\omega$ primitive for that if you know that $\left(\frac {ab}p\right)=\left(\frac ap\right)\left(\frac bp\right)$: Let $\omega$ be any residue with $\left(\frac\omega p\right)=-1$. Then $a\mapsto \omega a$ is an injective map from the set of quadratic residues to the set of non-residues, as well as vice versa. We concolude that both sets have same cardinality.

$\endgroup$
2
  • $\begingroup$ I am supposed to use the fact that $\omega$ is primitive. And that the legendre symbol is -1. $\endgroup$ – Ineedhelppls Jan 29 '16 at 13:33
  • 1
    $\begingroup$ @Ineedhelppls Fine, but one of these two factlets is irrelevant for the proof (though you may have used the existence of primitive roots to show the multiplicativity $\left(\frac {ab}p\right)=\left(\frac ap\right)\left(\frac bp\right)$ that I used) $\endgroup$ – Hagen von Eitzen Jan 29 '16 at 16:32

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.