This site is supported by donations to The OEIS Foundation.
Quadratic residues
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.