TOPICS
Search

Quadratic Nonresidue


If there is no integer 0<x<p such that

 x^2=q (mod p),

i.e., if the congruence (35) has no solution, then q is said to be a quadratic nonresidue (mod p). If the congruence (35) does have a solution, then q is said to be a quadratic residue (mod p).

In practice, it suffices to restrict the range to 0<x<=|_p/2_|, where |_x_| is the floor function, because of the symmetry (p-x)^2=x^2 (mod p).

Triangle of quadratic nonresidues

The following table summarizes the quadratic nonresidues for small p (OEIS A105640).

pquadratic nonresidues
1(none)
2(none)
32
42, 3
52, 3
62, 5
73, 5, 6
82, 3, 5, 6, 7
92, 3, 5, 6, 8
102, 3, 7, 8
112, 6, 7, 8, 10
122, 3, 5, 6, 7, 8, 10, 11
132, 5, 6, 7, 8, 11
143, 5, 6, 10, 12, 13
152, 3, 5, 7, 8, 11, 12, 13, 14
162, 3, 5, 6, 7, 8, 10, 11, 12, 13, 14, 15
173, 5, 6, 7, 10, 11, 12, 14
182, 3, 5, 6, 8, 11, 12, 14, 15, 17
192, 3, 8, 10, 12, 13, 14, 15, 18
202, 3, 6, 7, 8, 10, 11, 12, 13, 14, 15, 17, 18, 19
QuadraticNonresidueCounts

The numbers of quadratic nonresidues (mod p) for p=1, 2, ... are 0, 0, 1, 2, 2, 2, 3, 5, 5, 4, 5, 8, 6, 6, ... (OEIS A095972).

The smallest quadratic nonresidues for p=3, 4, ... are 2, 2, 2, 2, 3, 2, 2, 2, 2, 2, 2, 3, 2, 2, 3, 2, 2, ... (OEIS A020649). The smallest quadratic nonresidues for p=2, 3, 5, 7, 11, ... are 2, 2, 2, 3, 2, 2, 3, 2, 5, 2, 3, 2, 3, ... (OEIS A053760).

If the extended Riemann hypothesis is true, then the first quadratic nonresidue of a number (mod p) is always less than 3(lnp)^2/2 (Wedeniwski 2001) for p>3.

The following table gives the values of p such that the least quadratic nonresidue is n for small n.

nOEISp such that n is the smallest quadratic nonresidue
2A0250203, 4, 5, 6, 8, 9, 10, 11, 12, 13, 15, ...
3A0250217, 14, 17, 31, 34, 41, 49, 62, 79, 82, ...
5A02502223, 46, 47, 73, 94, 97, 146, 167, 193, ...
7A02502371, 142, 191, 239, 241, 359, 382, ...

See also

Quadratic Residue

Explore with Wolfram|Alpha

References

Sloane, N. J. A. Sequences A020649, A025020, A025021, A025022, A025023, A053760, A095972, and A105640 in "The On-Line Encyclopedia of Integer Sequences."Wedeniwski, S. "Primality Tests on Commutator Curves." Dissertation. Tübingen, Germany, 2001. http://www.hipilib.de/prime/primality-tests-on-commutator-curves.pdf.

Referenced on Wolfram|Alpha

Quadratic Nonresidue

Cite this as:

Weisstein, Eric W. "Quadratic Nonresidue." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/QuadraticNonresidue.html

Subject classifications