number of quadratic residues and nonresidues modulo p odd prime

Question

I read that for odd prime $p$, number of quadratic residues modulo $p$ is $\frac{p+1}{2}$ including $0$ and the number of nonresidues are $\frac{p-1}{2}$.

Could you help me see this? Is this a specific case of a more general result?

Answer 1

For an odd prime $p$, we have:

$$x^2 \equiv (p-x)^2 \pmod p$$

So there are at most $\frac{p-1}{2}$ non-zero quadratic residues, and at most $\frac{p+1}{2}$ quadratic residues counting zero.

Now, using $a,b\in\left\{1\dots\frac{p-1}{2}\right\}$, we produce $\frac{p-1}{2}$ different quadratic residues, because if $a^2\equiv b^2 \pmod p$ with $a\ne b$, and $1\le a,b\le\frac{p-1}{2}$, we have

$$(a-b)(a+b) \equiv 0 \pmod p$$

and as we have neither $p|(a-b)$ nor $p|(a+b)$, this is impossible.

As we have $\frac{p+1}{2}$ quadratic residues, we have $p-\frac{p+1}{2}=\frac{p-1}{2}$ non-quadratic residues.

Answer 2

May I add some information of an interesting arithmetic nature ? Although the sets $R$ of quadratic residues (exclusing $0$) and $NR$ of non residues mod $p$ in {$1, p-1/2$} have the same cardinality, their elements are not "equally distributed". For example:

1) Consider the real quadratic field $\mathbf Q (\sqrt p)$, with $p\equiv 1$ mod $4$ and hence of discriminant $p$. It is a general property of a real quadratic field $K$ with discriminant $D$ that there exists a fundamental unit $\epsilon >1$ of $K$such that $\epsilon^h = \eta$, where $\eta := \prod sin(\pi b/D)/\prod sin (\pi a/D)$, for $a\in R, b\in NR$ and $h$ is the class number of $K$. Since the function $sin$ is increasing in {$0, \pi/2$}, it follows that the values $sin(\pi b/D)$ are "on average" larger than the $sin (\pi a/D)$, i.e. that the elements of $R$ are "concentrated" at the beginning of the interval {$0, p/2$} and those of $NR$ at the end.

2) In the same vein, consider the imaginary quadratic field $\mathbf Q (\sqrt -p)$, with $p\equiv 3$ mod $4$, hence of discriminant $-p$. A classical analytic formula for the class number of an imaginary quadratic field implies that $h = \rho - \nu$ if $p\equiv 7$ mod $8$, $(\rho - \nu)/3$ if $p\equiv 3$ mod $8$, where $\rho =$ card $(R\cap$ {0, p/2}) and $\nu=$ card$(R\cap$ {0, p/2}).

For more properties and details, see e.g. Borevitch-Shafarevitch, chap. V, §3.