How can I use primitive roots to prove that there are the same number of quadratic residues as non-residues?

Question

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$.

Answer 1

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$

Answer 2

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.

Answer 3

This question was posted a while ago, and I am not going to directly answer the question, but instead make an important point: it is overkill to use primitive elements mod $p$ in order to show there are as many (nonzero) squares as nonsquares mod $p$ when $p$ is an odd prime. All you need to get the desired result are elementary properties of modular arithmetic for a prime modulus.

For integers $a$ and $b$, we have $a^2 \equiv b^2 \bmod p$ if and only if $(a+b)(a-b) \equiv 0 \bmod p$, and that is equivalent to $a+b \equiv 0 \bmod p$ or $a-b \equiv 0 \bmod p$ since $p$ is prime. Therefore $a^2 \equiv b^2 \bmod p$ if and only if $a \equiv \pm b \bmod p$. That means squaring on nonzero numbers mod $p$ is a 2-to-1 function, just like in the real numbers.

The nonzero numbers mod $p$ can be written as $1, 2, 3, \ldots, p-1 \bmod p$ and the second half of the list is negatives of the first half of the list: $p-1 \equiv -1 \bmod p$, $p-2 \equiv -2 \bmod p$, and so on down to $(p+1)/2 = -(p-1)/2 \bmod p$. Therefore the nonzero squares without repetition come from squaring the first half of the nonzero numbers mod $p$: $$ 1^2, 2^2, 3^2, \ldots, \left(\frac{p-1}{2}\right)^2 \bmod p. $$ That is $(p-1)/2$ different nonzero numbers mod $p$. There are $p-1$ nonzero numbers mod $p$, so half the nonzero numbers mod $p$ are quadratic residues and half are non-residues. In particular, there are quadratic nonresidues mod $p$.

To understand the structure of $n$th powers mod $p$ when $n$ is an arbitrary positive integer is greatly facilitated by knowing the nonzero numbers mod $p$ have a primitive root, but I think it is a bad idea to make students analyze the case $n=2$ by relying on primitive roots the first time, because it suggests that the result for $n=2$ is a more profound result than it really is. In particular, since the count of quadratic residues and nonresidues mod $p$ is the starting point for quadratic reciprocity, using primitive roots at this early stage suggests that quadratic reciprocity depends on the existence of primitive roots and that's incorrect: nowhere in the development of the quadratic reciprocity law is the existence of primitive roots required. I cringe when I see elementary number theory books apply the existence of primitive roots to show there are as many quadratic residues as nonresidues modulo an odd prime.