This site is supported by donations to The OEIS Foundation.

Quadratic residues

From OeisWiki
(Redirected from Quadratic residue)
Jump to: navigation, search

This article page is a 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.