Processing math: 100%
Skip to main content
Library homepage
 

Text Color

Text Size

 

Margin Size

 

Font Type

Enable Dyslexic Font
Mathematics LibreTexts

5.4: Introduction to Quadratic Residues and Nonresidues

( \newcommand{\kernel}{\mathrm{null}\,}\)

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 x2a(mod m) is solvable. If the congruence x2a(mod m) has no solution, then a is a quadratic nonresidue of m.

Notice that 12=621(mod 7), 32=422(mod 7) and 22=524(mod 7). Thus 1,2,4 are quadratic residues modulo 7 while 3,5,6 are quadratic nonresidues modulo 7.

Let p2 be a prime number and a is an integer such that pa. Then either a is quadratic nonresidue modulo p or x2a(mod p) has exactly two incongruent solutions modulo p.

If x2a(mod p) has a solution, say x=x, then x is a solution as well. Notice that xx(mod p) because then p2x and hence px0.

We now show that there are no more than two incongruent solutions. Assume that x=x and x=x are both solutions of x2a(mod p). Then we have (x)2(x)2=(x+x)(xx)0(mod p). Hence xx(mod p)  or  xx(mod p).

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

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

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

Exercises

  1. Find all the quadratic residues of 3.
  2. Find all the quadratic residues of 13.
  3. find all the quadratic residues of 18.
  4. Show that if p is prime and p7, 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.
  5. Show that if p is prime and p7, 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.


This page titled 5.4: Introduction to Quadratic Residues and Nonresidues is shared under a CC BY license and was authored, remixed, and/or curated by Wissam Raji.

  • Was this article helpful?

Support Center

How can we help?