This site is supported by donations to The OEIS Foundation.

# Quadratic residues

**stub**, please help by expanding it.

Given an integer and an odd prime , the former is a **quadratic residue** of the latter if the congruence has a solution. For example, 4 is a quadratic residue of 7 since .

There is a function that tells us whether is a quadratic residue of or not by returning 1 if that is the case and –1 otherwise. This function is called the Legendre symbol and is confusingly notated .

To determine whether a given integer is a quadratic residue of a given prime, we *could* iterate until finding a value such that , but this would be a huge waste of time if is not a quadratic residue of .

A somewhat better approach is to compute the squares modulo . 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 or : if the former then 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 , 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 th prime.