5.4: Introduction to Quadratic Residues and Nonresidues

Last updated
Save as PDF

Page ID: 8848

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

The question that we need to answer in this section is the following. If \(p\) is an odd prime and \(a\) is an integer relatively prime to \(p\). Is \(a\) a perfect square modulo \(p\).

Let \(m\) be a positive integer. An integer \(a\) is a quadratic residue of \(m\) if \((a,m)=1\) and the congruence \(x^2\equiv a (mod \ m)\) is solvable. If the congruence \(x^2\equiv a (mod \ m)\) has no solution, then \(a\) is a quadratic nonresidue of \(m\).

Notice that \(1^2=6^2\equiv 1(mod \ 7)\), \(3^2=4^2\equiv 2(mod \ 7)\) and \(2^2=5^2\equiv 4(mod \ 7)\). Thus \(1,2,4\) are quadratic residues modulo 7 while \(3,5,6\) are quadratic nonresidues modulo 7.

Let \(p\neq 2\) be a prime number and \(a\) is an integer such that \(p\nmid a\). Then either a is quadratic nonresidue modulo \(p\) or \[x^2\equiv a(mod \ p)\] has exactly two incongruent solutions modulo \(p\).

If \(x^2\equiv a(mod \ p)\) has a solution, say \(x=x'\), then \(-x'\) is a solution as well. Notice that \(-x' \not\equiv x'(mod \ p)\) because then \(p\mid 2x'\) and hence \(p\nmid x_0\).

We now show that there are no more than two incongruent solutions. Assume that \(x=x'\) and \(x=x''\) are both solutions of \(x^2\equiv a(mod \ p)\). Then we have \[(x')^2- (x'')^2=(x'+x'')(x'-x'')\equiv 0(mod \ p).\] Hence \[x'\equiv x''(mod \ p)\ \ \mbox{or} \ \ x'\equiv -x''(mod \ p).\]

The following theorem determines the number of integers that are quadratic residues modulo an odd prime.

If \(p\neq 2\) is a prime, then there are exactly \((p-1)/2\) quadratic residues modulo \(p\) and \((p-1)/2\) quadratic nonresidues modulo \(p\) in the set of integers \(1,2...,p-1\).

To find all the quadratic residues of \(p\) among all the integers \(1,2,...,p-1\), we determine the least positive residue modulo \(p\) of \(1^2,2^2,...,(p-1)^2\). Considering the \(p-1\) congruences and because each congruence has either no solution or two incongruent solutions, there must be exactly \((p-1)/2\) quadratic residues of \(p\) among \(1,2,...,p-1\). Thus the remaining are \((p-1)/2\) quadratic nonresidues of \(p\).

Exercises

Find all the quadratic residues of 3.
Find all the quadratic residues of 13.
find all the quadratic residues of 18.
Show that if \(p\) is prime and \(p\geq 7\), then there are always two consecutive quadratic residues of \(p\). Hint: Show that at least one of \(2,5\) or 10 is a quadratic residue of \(p\).
Show that if \(p\) is prime and \(p\geq 7\), then there are always two quadratic residues of \(p\) that differ by 3.

Contributors and Attributions

Dr. Wissam Raji, Ph.D., of the American University in Beirut. His work was selected by the Saylor Foundation’s Open Textbook Challenge for public release under a Creative Commons Attribution (CC BY) license.