An integer $a$ is a quadratic residue modulo $p$ if $a \equiv x^2 \pmod p$ for some integer $x$. If $a$ is not a quadratic residue modulo $p$, it is said to be a quadratic nonresidue modulo $p$.

An integer $a$ is a quadratic residue modulo $p$ if $a \equiv x^2 \pmod p$ for some integer $x$. If $a$ is not a quadratic residue modulo $p$, it is said to be a quadratic nonresidue modulo $p$.

In the case where $p$ is an odd prime, we often make use of the Legendre symbol

$$\left(\frac{a}{p}\right) = \begin{cases} 0 & p \mid a\\\ 1 & a\ \text{is a quadratic residue modulo}\ p\ \text{and}\ p \not\mid a\\\ -1 & a\ \text{is a quadratic nonresidue modulo}\ p. \end{cases}$$

There are $\frac{p-1}{2}$ quadratic residues (and nonresidues) for an odd prime $p$.

A powerful result regarding quadratic residues is the Law of Quadratic Reciprocity:

If $p$ and $q$ are odd primes, then $$\left(\frac{p}{q}\right) = \left(\frac{q}{p}\right)(-1)^{\frac{p-1}{2}\frac{q-1}{2}}.$$

history | excerpt history