representants of quadratic residues

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

$1^2,{\mathrm{\hspace{0.17em}2}}^2,\mathrm{\dots },{\left({\displaystyle \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(modp)$  would imply

$$p\mid a+b\mathit{\hspace{1em}}\text{or}\mathit{\hspace{1em}}p\mid a-b,$$

which is impossible when $a$ and $b$ are different integers among $1,\mathrm{\hspace{0.17em}2},\mathrm{\dots },\frac{p-1}{2}$.  Third, if $c$ is any quadratic residue modulo $p$, and therefore the congruence  $x^2\equiv c(modp)$  has a solution $x$, then $x$ is congruent with one of the numbers

$$\pm 1,\pm 2,\mathrm{\dots },\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
Canonical name	RepresentantsOfQuadraticResidues
Date of creation	2013-03-22 19:00:35
Last modified on	2013-03-22 19:00:35
Owner	pahio (2872)
Last modified by	pahio (2872)
Numerical id	7
Author	pahio (2872)
Entry type	Theorem
Classification	msc 11A15
Synonym	representant system of quadratic residues
Related topic	GaussianSum
Related topic	DifferenceOfSquares
Related topic	DivisibilityByPrimeNumber