Tag Info

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}}.$$