If there is an integer such that

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

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

	(2)
	(3)
	(4)

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

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

The numbers of quadratic residues (mod n) for n = 1, 2, ... are 0, 1, 1, 1, 2, 3, 3, 2, 3, 5, 5, 3, 6, 7, 5, 3, ... (Sloane's A105612).

The largest quadratic residues for p = 2, 3, ... are 1, 1, 1, 4, 4, 4, 4, 7, 9, 9, 9, 12, 11, ... (Sloane's A047210).

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

If

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

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

Given p and q in the congruence

x can be explicitly computed for p and q of certain special forms:

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

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

gives
and a solution to the quadratic congruence is

Schoof (1985) gives an algorithm for finding x with running time (Hardy et al. 1990). The congruence is solved by the Mathematica command SqrtMod[q, p] in the Mathematica add-on package NumberTheory`NumberTheoryFunctions` (which can be loaded with the command <<NumberTheory`).

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

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

for the nth convergent gives

Therefore, is a quadratic residue of D. 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 D. This method is not guaranteed to produce all quadratic residues, but can often produce several small ones in the case of large D, enabling D to be factored.

The number of squares s(n) in is related to the number q(n) of quadratic residues in by

for (Stangl 1996). Both q and s are multiplicative functions.

 

Associate, Euler's Criterion, Jacobi Symbol, Kronecker Symbol, Legendre Symbol, Multiplicative Function, Quadratic, Quadratic Nonresidue, Quadratic Reciprocity Theorem, Riemann Hypothesis