A quadratic residue modulo a positive integer 
is an integer 
for which the congruence
 |
(1)
|
has an integer solution 
. Except where stated otherwise, the lists and counts
below exclude the zero residue class, following
Hardy and Wright (1979, p. 67), so their counts are one less than the numbers
of squares modulo 
. Other conventions include 0.
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 indicate that 
is a quadratic residue or quadratic
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 nonzero quadratic residues (mod 10) are
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 nonzero quadratic residues for 
is given below (OEIS A046071),
with those integers 
not in the list being quadratic
nonresidues modulo 
.
 | quadratic residues |
| 1 | (none) |
| 2 | 1 |
| 3 | 1 |
| 4 | 1 |
| 5 | 1, 4 |
| 6 | 1, 3, 4 |
| 7 | 1, 2, 4 |
| 8 | 1, 4 |
| 9 | 1, 4, 7 |
| 10 | 1, 4, 5, 6, 9 |
| 11 | 1, 3, 4, 5, 9 |
| 12 | 1, 4, 9 |
| 13 | 1, 3, 4, 9, 10, 12 |
| 14 | 1, 2, 4, 7, 8, 9, 11 |
| 15 | 1, 4, 6, 9, 10 |
| 16 | 1, 4, 9 |
| 17 | 1, 2, 4, 8, 9, 13, 15, 16 |
| 18 | 1, 4, 7, 9, 10, 13, 16 |
| 19 | 1, 4, 5, 6, 7, 9, 11, 16, 17 |
| 20 | 1, 4, 5, 9, 16 |
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).
For a composite number as modulus, one may instead restrict quadratic residues to squares of units in the modulo multiplication group, as Stangl
(1996) does. Such a residue is represented by 
with 
relatively prime to the
modulus. The unit squares modulo 
are illustrated below (OEIS A096103),
and their numbers 
for 
,
2, ... are 1, 1, 1, 1, 2, 1, 3, 1, 3, 2, 5, 1, 6, ... (OEIS A046073),
with 
for the one-element modulo multiplication
group. If 
counts all squares in 
, including 0, then
 |
(5)
|
for 
and 
an odd prime (Stangl 1996). Both 
and 
are multiplicative
functions, with 
.
 | unit squares (mod  ) |
| 2 | 1 |
| 3 | 1 |
| 4 | 1 |
| 5 | 1, 4 |
| 6 | 1 |
| 7 | 1, 2, 4 |
| 8 | 1 |
| 9 | 1, 4, 7 |
Given an odd prime 
and an integer 
, then the Legendre symbol
is given by
 |
(6)
|
For an integer 
not divisible by 
, Euler's criterion gives
 |
(7)
|
where the sign is positive for a quadratic residue and negative for a quadratic nonresidue. If 
is a quadratic residue, then there is an integer 
not divisible
by 
such that 
,
so
 |
(8)
|
and 
is congruent to 1 (mod 
) by Fermat's little theorem.
Given an odd prime 
and a nonzero quadratic residue 
modulo 
in the congruence
 |
(9)
|
can be explicitly computed for 
and 
of certain special forms:
 |
(10)
|
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 nonzero quadratic residue modulo an odd prime 
. Choose an integer 
such that the Legendre
symbol 
.
Then defining
 |  |  |
(11)
|
 |  |  |
(12)
|
 |  |  |
(13)
|
gives, for positive integer 
,
 |  |  |
(14)
|
 |  |  |
(15)
|
and a solution to the quadratic congruence is
 |
(16)
|
For a fixed integer 
, Schoof (1985, p. 483) gives a deterministic algorithm
for finding a square root of 
modulo 
using 
bit operations, with the implied constant depending
on 
.
The congruence can be solved by the Wolfram
Language command PowerMod[q,
1/2, p].
Kunerth (1878, pp. 338-341) described a method for a prime number modulus that uses suitable rational solutions of auxiliary quadratic equations. A difference of squares and a further congruence then give an integer solution of the original congruence. Finding the required auxiliary solutions and solving the final congruence are part of the computation.
The following table gives the odd primes 
not divisible by 
which have the integer 
as a quadratic residue, where 
is an integer.
 | primes |
 |  ,  ,  ,  |
 |  ,  ,  ,  |
 |  |
 |  ,  |
 |  |
| 2 |  |
| 3 |  |
| 5 |  |
| 6 |  ,  |
For a positive integer 
that is not a square number,
write the successive tails of the simple
continued fraction of 
as 
, starting with 
and 
. If 
, where 
is the floor function,
then 
and
 |
(17)
|
for 
.
These parameters are distinct from the numerator and
denominator of a convergent.
Let ![h_n/k_n=[a_1;a_2,...,a_n]](/images/equations/QuadraticResidue/Inline127.svg)
be the 
th
convergent. Then
 |
(18)
|
so 
is a quadratic residue modulo 
. Together with 
, this shows that 
is a quadratic residue for every positive
integer 
.
This method is not guaranteed to produce every quadratic residue, but can produce
several small signed residues for large 
, which are useful in finding a prime
factorization.
in Coprime Integers 
and 
." Math. Comput. 55, 327-343, 1990.Hilton,
P.; Holton, D.; and Pedersen, J. 
."
Math. Comput. 44, 483-494, 1985. 
." Math. Mag. 69, 285-289, 1996.Tonelli,
A. "Bemerkung über die Auflösung quadratischer Congruenzen."
Göttingen Nachr., 344-346, 1891.Wagon, S. "Quadratic
Residues." §9.2 in