Theorem.  Let $p$ be a positive odd prime number.  Then the integers

 $\displaystyle 1^{2},\,2^{2},\,\ldots,\,\left(\frac{p\!-\!1}{2}\right)^{\!2}$ (1)

constitute a representant system of incongruent quadratic residues modulo $p$.  Accordingly, there are $\frac{p\!-\!1}{2}$ quadratic residues and equally many nonresidues modulo $p$.

Proof.  Firstly, the numbers (1), being squares, are quadratic residues modulo $p$.  Secondly, they are incongruent, because a congruence$a^{2}\equiv b^{2}\pmod{p}$  would imply

 $p\mid a\!+\!b\quad\mbox{or}\quad p\mid a\!-\!b,$

which is impossible when $a$ and $b$ are different integers among $1,\,2,\,\ldots,\,\frac{p\!-\!1}{2}$.  Third, if $c$ is any quadratic residue modulo $p$, and therefore the congruence  $x^{2}\equiv c\pmod{p}$  has a solution $x$, then $x$ is congruent with one of the numbers

 $\pm 1,\,\pm 2,\,\ldots,\,\pm\frac{p\!-\!1}{2}$

which form a reduced residue system modulo $p$ (see absolutely least remainders).  Then $x^{2}$ and $c$ are congruent with one of the numbers (1).

Title representants of quadratic residues RepresentantsOfQuadraticResidues 2013-03-22 19:00:35 2013-03-22 19:00:35 pahio (2872) pahio (2872) 7 pahio (2872) Theorem msc 11A15 representant system of quadratic residues GaussianSum DifferenceOfSquares DivisibilityByPrimeNumber