## You are here

Homerepresentants of quadratic residues

## Primary tabs

# representants of quadratic residues

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 complete 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}\;\;(\mathop{{\rm mod}}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\;\;(\mathop{{\rm mod}}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).

## Mathematics Subject Classification

11A15*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections