Orders and quadratic residues · Definition

Quadratic residue

elementary number theoryorders and quadratic residues

Before you start you need to know

Quadratic residues answer a simple question: which numbers are perfect squares modulo n. Their study underlies quadratic reciprocity and many primality algorithms.

Definition

A quadratic residue modulo n is an integer a with gcd(a,n)=1 such that the congruence x² ≡ a (mod n) has a solution. If it has no solution, a is a quadratic nonresidue.

\[x^2 \equiv a \pmod{p}\]

If p is an odd prime, exactly half of the nonzero residue classes modulo p are quadratic residues, since x² ≡ y² (mod p) is equivalent to y ≡ ±x (mod p). Thus the residues form a subset of size (p−1)/2 among the nonzero classes.

Modulo 7, the squares of 1, 2, 3 are 1, 4, 2. So the nonzero quadratic residues are {1, 2, 4} and the nonresidues are {3, 5, 6}, which can be checked by raising each residue to the power (7−1)/2 = 3 and comparing.

A typical mistake is forgetting the condition gcd(a,n)=1: multiples of p can satisfy x² ≡ a with a solution, but they are not counted as residues in the standard sense. Nor should one confuse residues with solvability in composite moduli, where the count changes.

Think about it

What is Euler's criterion \(a^{(p-1)/2}\) used for, with \(p\) an odd prime?

It decides whether a is a residue without listing squares: a is a residue if \(a^{(p-1)/2} \equiv 1 \pmod{p}\) and a nonresidue if \(a^{(p-1)/2} \equiv -1 \pmod{p}\).

Exercises 10

  1. Which of these integers is a quadratic residue modulo 7?
  2. State the definition of a quadratic residue modulo n for an integer a with gcd(a,n)=1.
  3. What is the set of nonzero quadratic residues modulo 5?
  4. Give the number of nonzero quadratic residues modulo an odd prime p.
  5. Which of these residues is a quadratic nonresidue modulo 11?
  6. Compute the nonzero quadratic residues modulo 9 and state how many there are.
  7. Decide whether 2 is a quadratic residue modulo 17 by computing the squares of the residues from 1 to 8.
  8. Solve x² ≡ 4 (mod 15) and count how many solutions exist modulo 15.
  9. Determine whether 3 is a quadratic residue modulo 13 by testing the squares of 1 through 6.
  10. Let \(p = 13\), \(a = 4\) and \(b = 9\) be quadratic residues modulo 13. Prove that \(ab\) is also one and find a square root of \(ab\) modulo 13.

References

  • David M. Burton, Elementary Number Theory, 7th edition, McGraw-Hill, 2011. cap. 9
  • Ivan Niven, Herbert S. Zuckerman, Hugh L. Montgomery, An Introduction to the Theory of Numbers, 5th edition, Wiley, 1991. cap. 3