This site is supported by donations to The OEIS Foundation.

(Redirected from Quadratic residue)

Given an integer ${\displaystyle a}$ and an odd prime ${\displaystyle p}$, the former is a quadratic residue of the latter if the congruence ${\displaystyle x^{2}\equiv a\mod p}$ has a solution. For example, 4 is a quadratic residue of 7 since ${\displaystyle 5^{2}\equiv 4\mod 7}$.

There is a function ${\displaystyle f(a,p)}$ that tells us whether ${\displaystyle a}$ is a quadratic residue of ${\displaystyle p}$ or not by returning 1 if that is the case and –1 otherwise. This function is called the Legendre symbol and is confusingly notated ${\displaystyle \left({\frac {a}{p}}\right)}$.

To determine whether a given integer is a quadratic residue of a given prime, we could iterate ${\displaystyle k}$ until finding a value such that ${\displaystyle {\sqrt {kp+a}}\in \mathbb {Z} }$, but this would be a huge waste of time if ${\displaystyle a}$ is not a quadratic residue of ${\displaystyle p}$.

A somewhat better approach is to compute the ${\displaystyle p}$ squares modulo ${\displaystyle p}$. This is straightforward for small primes, like our example 7, for which we see that 4 is among {1, 4, 2, 2, 4, 1, 0}, in fact appearing twice. But for larger primes that quickly becomes impractical.

The best way is to see whether ${\displaystyle a^{\frac {p-1}{2}}\equiv p-1\mod p}$ or ${\displaystyle a^{\frac {p-1}{2}}\equiv 1\mod p}$: if the former then ${\displaystyle a}$ is not a quadratic residue, if the latter it is. In our example with 4, we see that 4 cubed is 64, which is one more than 63, a multiple of 7. We see that 5 is not a quadratic residue of 7 because ${\displaystyle 5^{3}=125\equiv 6\mod 7}$, or 7 – 1 (thus justifying why the Legendre symbol gives 1 or –1 as its result).

See A063987 for an irregular array giving quadratic residues modulo the ${\displaystyle n}$th prime.