Quadratic Nonresidue

👁 DOWNLOAD Mathematica Notebook
Download Wolfram Notebook

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

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)
.

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

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
.

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 Resource. https://mathworld.wolfram.com/QuadraticNonresidue.html

Subject classifications