Quadratic residues

This article page is a stub, please help by expanding it.

---

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

There is a function $f(a,p)$ that tells us whether $a$ is a quadratic residue of $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 $\left({\frac {a}{p}}\right)$.

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

A somewhat better approach is to compute the $p$ squares modulo $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 $a^{\frac {p-1}{2}}\equiv p-1\mod p$ or $a^{\frac {p-1}{2}}\equiv 1\mod p$: if the former then $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 $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 $n$th prime.