TOPICS
Search

Quadratic Residue


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

 x^2=q (mod p),
(1)

i.e., the congruence (1) has a solution, then q is said to be a quadratic residue (mod p). Note that the trivial case q=0 is generally excluded from lists of quadratic residues (e.g., Hardy and Wright 1979, p. 67) so that the number of quadratic residues (mod n) is taken to be one less than the number of squares (mod n). However, other sources include 0 as a quadratic residue.

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

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

For example, 4^2=6 (mod 10), 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

1^2=1 (mod 10)  2^2=4 (mod 10)  3^2=9 (mod 10)
(2)
4^2=6 (mod 10)  5^2=5 (mod 10)  6^2=6 (mod 10)
(3)
7^2=9 (mod 10)  8^2=4 (mod 10)  9^2=1 (mod 10),
(4)

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

Quadratic residues

A list of quadratic residues for p<=20 is given below (OEIS A046071), with those numbers <p not in the list being quadratic nonresidues of p.

pquadratic residues
1(none)
21
31
41
51, 4
61, 3, 4
71, 2, 4
81, 4
91, 4, 7
101, 4, 5, 6, 9
111, 3, 4, 5, 9
121, 4, 9
131, 3, 4, 9, 10, 12
141, 2, 4, 7, 8, 9, 11
151, 4, 6, 9, 10
161, 4, 9
171, 2, 4, 8, 9, 13, 15, 16
181, 4, 7, 9, 10, 13, 16
191, 4, 5, 6, 7, 9, 11, 16, 17
201, 4, 5, 9, 16
QuadraticResidueNumbers

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, ... (OEIS A105612).

Largest quadratic residue binary plot

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

Care must be taken when dealing with quadratic residues, as slightly different definitions are also apparently sometimes used. For example, Stangl (1996) adopts the apparently nonstandard definition of quadratic residue as an integer x satisfying 0<x<p such that x^2=q (mod p) and x is relatively prime to p. This definition therefore excludes non-units (mod p). By this definition, the quadratic residues (mod n) for n=1, 2, ... are illustrated below (OEIS A096103, the numbers of them are given by 0, 1, 1, 1, 2, 1, 3, 1, 3, 2, 5, 1, 6, ... (OEIS A046073) and the number of squares s(n) in Z_n is related to the number q(n) of quadratic residues in Z_n by

 q(p^n)=s(p^n)-s(p^(n-2))
(5)

for n>=3 and p an odd prime (Stangl 1996). (Note that both q and s are multiplicative functions.)

nnon-unit squares (mod n)
21
31
41
51, 4
61
71, 2, 4
81
91, 4, 7

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

 (a/p)={1   if a is a quadratic residue mod p; -1   otherwise.
(6)

If

 r^((p-1)/2)=+/-1 (mod p),
(7)

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 x^2 such that r=x^2 (mod p), so

 r^((p-1)/2)=(x^2)^((p-1)/2)=x^(p-1) (mod p),
(8)

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

Given p and q in the congruence

 x^2=q (mod p),
(9)

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

 x={q^(k+1) (mod p)   for p=4k+3; q^(k+1) (mod p)   for p=8k+5 and q^(2k+1)=1 (mod p); 1/2(4q)^(k+1)(p+1) (mod p)   for p=8k+5 and q^(2k+1)=-1 (mod p).
(10)

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 (h^2-4q/p)=-1. Then defining

V_1=h
(11)
V_2=h^2-2q
(12)
V_i=hV_(i-1)-qV_(i-2)    for i>=3,
(13)

gives

V_(2i)=V_i^2-2q^i
(14)
V_(2i+1)=V_iV_(i+1)-hq^i,
(15)

and a solution to the quadratic congruence is

 x=1/2(p+1)V_((p+1)/2) (mod p).
(16)

Schoof (1985) gives an algorithm for finding x with running time O(ln^(10)n) (Hardy et al. 1990). The congruence can solved by the Wolfram Language command PowerMod[q, 1/2, p].

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

dprimes
-624k+1,5,7,11
-520k+1,3,7,9
-36k+1
-28k+1,3
-14k+1
28k+/-1
312k+/-1
510k+/-1
624k+/-1,5

Finding the continued fraction of a square root sqrt(D) and using the relationship

 Q_n=(D-P_n^2)/(Q_(n-1))
(17)

for the nth convergent P_n/Q_n gives

 P_n^2=-Q_nQ_(n-1) (mod D).
(18)

Therefore, -Q_nQ_(n-1) is a quadratic residue of D. But since Q_1=1, -Q_2 is a quadratic residue, as must be -Q_2Q_3. But since -Q_2 is a quadratic residue, so is Q_3, and we see that (-1)^(n-1)Q_n 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.


See also

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

Explore with Wolfram|Alpha

References

Burgess, D. A. "The Distribution of Quadratic Residues and Non-Residues." Mathematika 4, 106-112, 1975.Burton, D. M. Elementary Number Theory, 4th ed. New York: McGraw-Hill, p. 201, 1997.Courant, R. and Robbins, H. "Quadratic Residues." §2.3 in Supplement to Ch. 1 in What Is Mathematics?: An Elementary Approach to Ideas and Methods, 2nd ed. Oxford, England: Oxford University Press, pp. 38-40, 1996.Guy, R. K. "Quadratic Residues. Schur's Conjecture" and "Patterns of Quadratic Residues." §F5 and F6 in Unsolved Problems in Number Theory, 2nd ed. New York:Springer-Verlag, pp. 244-248, 1994.Hardy, K.; Muskat, J. B.; and Williams, K. S. "A Deterministic Algorithm for Solving n=fu^2+gv^2 in Coprime Integers u and v." Math. Comput. 55, 327-343, 1990.Hardy, G. H. and Wright, E. M. "Quadratic Residues." §6.5 in An Introduction to the Theory of Numbers, 5th ed. Oxford, England: Clarendon Press, pp. 67-68, 1979.Hilton, P.; Holton, D.; and Pedersen, J. Mathematical Reflections in a Room with Many Mirrors. New York:Springer-Verlag, p. 43, 1997.Jones, G. A. and Jones, J. M. "Quadratic Residues." Ch. 7 in Elementary Number Theory. Berlin:Springer-Verlag, pp. 119-141, 1998.Nagell, T. "Theory of Quadratic Residues." Ch. 4 in Introduction to Number Theory. New York: Wiley, pp. 115 and 132-155, 1951.Niven, I. and Zuckerman, H. An Introduction to the Theory of Numbers, 4th ed. New York: Wiley, p. 84, 1980.Rosen, K. H. Ch. 9 in Elementary Number Theory and Its Applications, 3rd ed. Reading, MA: Addison-Wesley, 1993.Schoof, R. "Elliptic Curves Over Finite Fields and the Computation of Square Roots mod p." Math. Comput. 44, 483-494, 1985.Séroul, R. "Quadratic Residues." §2.10 in Programming for Mathematicians. Berlin:Springer-Verlag, pp. 17-18, 2000.Shanks, D. Solved and Unsolved Problems in Number Theory, 4th ed. New York: Chelsea, pp. 63-66, 1993.Sloane, N. J. A. Sequences A046071, A046073, A047210, and A096103 in "The On-Line Encyclopedia of Integer Sequences."Stangl, W. D. "Counting Squares in Z_n." 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 Mathematica in Action. New York: W. H. Freeman, pp. 292-296, 1991.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 Residue

Cite this as:

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

Subject classifications