Quadratic Residue

If there is an integer  such that

(1)

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

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 indicated that  is a quadratic residue or 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 entire set of quadratic residues (mod 10) are given by 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 quadratic residues for  is given below (OEIS A046071), with those numbers  not in the list being quadratic nonresidues of .

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

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  satisfying  such that  and  is relatively prime to . This definition therefore excludes non-units (mod ). By this definition, the quadratic residues (mod ) for , 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  in  is related to the number  of quadratic residues in  by

(5)

for  and  an odd prime (Stangl 1996). (Note that both  and  are multiplicative functions.)

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

If

(7)

then  is a quadratic residue (+) or nonresidue (). This can be seen since if  is a quadratic residue of , then there exists a square  such that , so

(8)

and  is congruent to 1 (mod ) by Fermat's little theorem.

Given  and  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 quadratic residue modulo an odd prime . Choose  such that the Legendre symbol . Then defining

			(11)
			(12)
			(13)

gives

			(14)
			(15)

and a solution to the quadratic congruence is

(16)

Schoof (1985) gives an algorithm for finding  with running time  (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  as a quadratic residue.

	primes
2
3
5
6

Finding the continued fraction of a square root  and using the relationship

(17)

for the th convergent  gives

(18)

Therefore,  is a quadratic residue of . But since ,  is a quadratic residue, as must be . But since  is a quadratic residue, so is , and we see that  are all quadratic residues of . This method is not guaranteed to produce all quadratic residues, but can often produce several small ones in the case of large , enabling  to be factored.

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  in Coprime Integers  and ." 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 ." 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 ." 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. https://www.hipilib.de/prime/primality-tests-on-commutator-curves.pdf.