Quadratic Residue

If there is an Integer $x$ such that

$$x^2\equiv q\ \left({{\rm mod\ } {p}}\right),$$ (1)

then $q$ is said to be a quadratic residue (mod $p$). If not, $q$ is said to be a quadratic nonresidue (mod $p$). For example, $4^2\equiv 6\ \left({{\rm mod\ } {10}}\right)$, 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\equiv 1\ \left({{\rm mod\ } {10}}\right)\quad 2^2\equiv ... ...{10}}\right)\quad 3^2\equiv 9\ \left({{\rm mod\ } {10}}\right)$$

$$4^2\equiv 6\ \left({{\rm mod\ } {10}}\right)\quad 5^2\equiv ... ...{10}}\right)\quad 6^2\equiv 6\ \left({{\rm mod\ } {10}}\right)$$

$$7^2\equiv 9\ \left({{\rm mod\ } {10}}\right)\quad 8^2\equiv ... ...{10}}\right)\quad 9^2\equiv 1\ \left({{\rm mod\ } {10}}\right)$$

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

A list of quadratic residues for $p\leq 29$ is given below (Sloane's A046071), with those numbers $<p$ not in the list being quadratic nonresidues of $p$.

$p$	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

Given an Odd Prime $p$ and an Integer $a$, then the Legendre Symbol is given by

$$\left({a\over p}\right)=\cases{ 1 & if $a$\ is a quadratic residue mod $p$\cr -1 & otherwise.\cr}$$ (2)

If

$$r^{(p-1)/2}\equiv \pm 1\ \left({{\rm mod\ } {p}}\right),$$ (3)

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\equiv x^2\ \left({{\rm mod\ } {p}}\right)$, so

$$r^{(p-1)/2}\equiv (x^2)^{(p-1)/2} \equiv x^{p-1} {\rm\ (mod\ } p),$$ (4)

and $x^{p-1}$ is congruent to 1 (mod $p$) by Fermat's Little Theorem. $x$ is given by

$$\cases{ q^{k+1} {\rm\ (mod\ } p)\cr \quad{\rm for\ } p=4k+... ... and\ } q^{2k+1}\equiv -1\ \left({{\rm mod\ } {p}}\right).\cr}$$ (5)

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$$ (6)

$$V_2 = h^2-2q$$ (7)

$$V_i = hV_{i-1}-qV_{i-2} \qquad{\rm for\ } i\geq 3,$$ (8)

gives

$$V_{2i} = {V_i}^2-2q^i$$ (9)

$$V_{2i+1} = V_iV_{i+1}-hn^i,$$ (10)

and a solution to the quadratic Congruence is

$$x=V_{(p+1)/2} \left({p+1\over 2}\right){\rm\ (mod\ } p).$$ (11)

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

$d$	Primes
$-6$	$24k+1, 5, 7, 11$
$-5$	$20k+1, 3, 7, 9$
$-3$	$6k+1$
$-2$	$8k+1, 3$
$-1$	$4k+1$
2	$8k\pm 1$
3	$12k\pm 1$
5	$10k\pm 1$
6	$24k\pm 1,5$

Finding the Continued Fraction of a Square Root $\sqrt{D}$ and using the relationship

$$Q_n={D-{P_n}^2\over Q_{n-1}}$$ (12)

for the $n$th Convergent $P_n/Q_n$ gives

$${P_n}^2\equiv -Q_nQ_{n-1}\ \left({{\rm mod\ } {D}}\right).$$ (13)

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.

The number of Squares $s(n)$ in $\Bbb{Z}_n$ is related to the number $q(n)$ of quadratic residues in $\Bbb{Z}_n$ by

$$q(p^n)=s(p^n)-s(p^{n-2})$$ (14)

for $n\geq 3$ (Stangl 1996). Both $q$ and $s$ are Multiplicative Functions.

See also Euler's Criterion, Multiplicative Function, Quadratic Reciprocity Theorem, Riemann Hypothesis

References

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.

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.

Shanks, D. Solved and Unsolved Problems in Number Theory, 4th ed. New York: Chelsea, pp. 63-66, 1993.

Sloane, N. J. A. Sequence A046071 in ``The On-Line Version of the Encyclopedia of Integer Sequences.'' http://www.research.att.com/~njas/sequences/eisonline.html.

Stangl, W. D. ``Counting Squares in $\Bbb{Z}_n$.'' Math. Mag. 69, 285-289, 1996.

Wagon, S. ``Quadratic Residues.'' §9.2 in Mathematica in Action. New York: W. H. Freeman, pp. 292-296, 1991.