info prev up next book cdrom email home

Quadratic Residue

If there is an Integer $x$ such that

\begin{displaymath}
x^2\equiv q\ \left({{\rm mod\ } {p}}\right),
\end{displaymath} (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

\begin{displaymath}
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)
\end{displaymath}


\begin{displaymath}
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)
\end{displaymath}


\begin{displaymath}
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)
\end{displaymath}

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

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

If
\begin{displaymath}
r^{(p-1)/2}\equiv \pm 1\ \left({{\rm mod\ } {p}}\right),
\end{displaymath} (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
\begin{displaymath}
r^{(p-1)/2}\equiv (x^2)^{(p-1)/2} \equiv x^{p-1} {\rm\ (mod\ } p),
\end{displaymath} (4)

and $x^{p-1}$ is congruent to 1 (mod $p$) by Fermat's Little Theorem. $x$ is given by
\begin{displaymath}
\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}
\end{displaymath} (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

$\displaystyle V_1$ $\textstyle =$ $\displaystyle h$ (6)
$\displaystyle V_2$ $\textstyle =$ $\displaystyle h^2-2q$ (7)
$\displaystyle V_i$ $\textstyle =$ $\displaystyle hV_{i-1}-qV_{i-2} \qquad{\rm for\ } i\geq 3,$ (8)

gives
$\displaystyle V_{2i}$ $\textstyle =$ $\displaystyle {V_i}^2-2q^i$ (9)
$\displaystyle V_{2i+1}$ $\textstyle =$ $\displaystyle V_iV_{i+1}-hn^i,$ (10)

and a solution to the quadratic Congruence is
\begin{displaymath}
x=V_{(p+1)/2} \left({p+1\over 2}\right){\rm\ (mod\ } p).
\end{displaymath} (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

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

for the $n$th Convergent $P_n/Q_n$ gives
\begin{displaymath}
{P_n}^2\equiv -Q_nQ_{n-1}\ \left({{\rm mod\ } {D}}\right).
\end{displaymath} (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

\begin{displaymath}
q(p^n)=s(p^n)-s(p^{n-2})
\end{displaymath} (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.



info prev up next book cdrom email home

© 1996-9 Eric W. Weisstein
1999-05-25