Quadratic Residue

If there is an integer such that

i.e., the congruence (1) has a solution, then is said to be a quadratic residue (mod ). Note that the trivial case is generally excluded from lists of quadratic residues (e.g., Hardy and Wright 1979, p. 67) so that the number of quadratic residues (mod ) is taken to be one less than the number of squares (mod ). However, other sources include 0 as a quadratic residue.

If the congruence does not have a solution, then is said to be a quadratic nonresidue (mod ). Hardy and Wright (1979, pp. 67-68) use the shorthand notations and , to indicated that is a quadratic residue or nonresidue, respectively.

In practice, it suffices to restrict the range to , where is the floor function, because of the symmetry .

For example, , so 6 is a quadratic residue (mod 10). The entire set of quadratic residues (mod 10) are given by 1, 4, 5, 6, and 9, since

making the numbers 2, 3, 7, and 8 the quadratic nonresidues (mod 10).

A list of quadratic residues for is given below (OEIS A046071), with those numbers not in the list being quadratic nonresidues of .

The numbers of quadratic residues (mod ) for , 2, ... are 0, 1, 1, 1, 2, 3, 3, 2, 3, 5, 5, 3, 6, 7, 5, 3, ... (OEIS A105612).

The largest quadratic residues for , 3, ... are 1, 1, 1, 4, 4, 4, 4, 7, 9, 9, 9, 12, 11, ... (OEIS A047210).

Care must be taken when dealing with quadratic residues, as slightly different definitions are also apparently sometimes used. For example, Stangl (1996) adopts the apparently nonstandard definition of quadratic residue as an integer satisfying such that and is relatively prime to . This definition therefore excludes non-units (mod ). By this definition, the quadratic residues (mod ) for , 2, ... are illustrated below (OEIS A096103, the numbers of them are given by 0, 1, 1, 1, 2, 1, 3, 1, 3, 2, 5, 1, 6, ... (OEIS A046073) and the number of squares in is related to the number of quadratic residues in by

for and an odd prime (Stangl 1996). (Note that both and are multiplicative functions.)

Given an odd prime and an integer , then the Legendre symbol is given by

If

then is a quadratic residue (+) or nonresidue (). This can be seen since if is a quadratic residue of , then there exists a square such that , so

and is congruent to 1 (mod ) by Fermat's little theorem.

Given and in the congruence

can be explicitly computed for and of certain special forms:

For example, the first form can be used to find given the quadratic residues , 3, 4, 5, and 9 (mod , having ), whereas the second and third forms determine given the quadratic residues , 3, 4, 9, 10, and 12 (mod , having ), and , 3, 4, 7, 9, 10, 11, 12, 16, 21, 25, 26, 27, 28, 30, 33, 34, 36 (mod , having ).

More generally, let be a quadratic residue modulo an odd prime . Choose such that the Legendre symbol . Then defining

gives

and a solution to the quadratic congruence is

Schoof (1985) gives an algorithm for finding with running time (Hardy et al. 1990). The congruence can solved by the Wolfram Language command PowerMod[q, 1/2, p].

The following table gives the primes which have a given number as a quadratic residue.

Finding the continued fraction of a square root and using the relationship

for the th convergent gives

Therefore, is a quadratic residue of . But since , is a quadratic residue, as must be . But since is a quadratic residue, so is , and we see that are all quadratic residues of . This method is not guaranteed to produce all quadratic residues, but can often produce several small ones in the case of large , enabling to be factored.