A quadratic nonresidue modulo a positive integer 
is an integer 
for which the congruence
 |
has no integer solution 
. If this congruence
does have a solution, then 
is a quadratic residue
(mod 
).
In particular, 0 is a quadratic residue.
In practice, it suffices to restrict the range to 
, where 
is the floor function,
because of the symmetry 
.
The following table summarizes the quadratic nonresidues 
for small 
(OEIS A096013).
 | quadratic nonresidues |
| 1 | (none) |
| 2 | (none) |
| 3 | 2 |
| 4 | 2, 3 |
| 5 | 2, 3 |
| 6 | 2, 5 |
| 7 | 3, 5, 6 |
| 8 | 2, 3, 5, 6, 7 |
| 9 | 2, 3, 5, 6, 8 |
| 10 | 2, 3, 7, 8 |
| 11 | 2, 6, 7, 8, 10 |
| 12 | 2, 3, 5, 6, 7, 8, 10, 11 |
| 13 | 2, 5, 6, 7, 8, 11 |
| 14 | 3, 5, 6, 10, 12, 13 |
| 15 | 2, 3, 5, 7, 8, 11, 12, 13, 14 |
| 16 | 2, 3, 5, 6, 7, 8, 10, 11, 12, 13, 14, 15 |
| 17 | 3, 5, 6, 7, 10, 11, 12, 14 |
| 18 | 2, 3, 5, 6, 8, 11, 12, 14, 15, 17 |
| 19 | 2, 3, 8, 10, 12, 13, 14, 15, 18 |
| 20 | 2, 3, 6, 7, 8, 10, 11, 12, 13, 14, 15, 17, 18, 19 |
The numbers of quadratic nonresidues (mod 
) for 
, 2, ... are 0, 0, 1, 2, 2, 2, 3, 5, 5, 4, 5, 8, 6, 6, ...
(OEIS A095972).
The smallest quadratic nonresidues for 
, 4, ... are 2, 2, 2, 2, 3, 2, 2, 2, 2, 2, 2, 3, 2, 2, 3,
2, 2, ... (OEIS A020649). For the odd
primes 
,
5, 7, 11, ..., the smallest quadratic nonresidues are 2, 2, 3, 2, 2, 3, 2, 5, 2,
3, 2, 3, ... (OEIS A053760, omitting its initial
conventional value 2 for 
, which has no quadratic nonresidue).
If the extended Riemann hypothesis is true, then the least quadratic nonresidue modulo a positive
integer 
is less than 
(Wedeniwski 2001, p. 122).
The following table gives the values of 
such that the least quadratic nonresidue is 
for small 
.
such that 
is the smallest quadratic nonresidue