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$.
2
$\begingroup$
$\endgroup$
3
$\begingroup$
$\endgroup$
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$
-
$\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$
$\endgroup$
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.
answered Jan 28 '16 at 20:25
-
$\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
