Skip to content
Tutorials Center
My learning

Topics

Lesson 27 of 37 · Quadratic Residues

Quadratic Residues and Euler's Criterion

Learn which numbers are squares modulo a prime, count them, test membership with Euler's criterion, and take square roots when p is 3 mod 4.

In ordinary arithmetic, only some integers are perfect squares: 1, 4, 9, 16, ... Modulo a prime, something similar happens. Take p = 7. Squaring the numbers 1 to 6 gives 1, 4, 2, 2, 4, 1 modulo 7. Only 1, 2 and 4 appear; 3, 5 and 6 never do. The numbers that appear are called quadratic residues, the others non-residues.

Quadratic residues are the gateway to deep results: quadratic reciprocity, primality tests, square roots modulo p, and several cryptosystems. This lesson defines the idea, counts the residues, proves Euler's criterion in an experimental way, and shows the neat square-root shortcut for primes of the form 4k + 3.

Definitions

An integer a is a quadratic residue modulo n if gcd(a, n) = 1 and there is an x with x² ≡ a (mod n). If no such x exists, a is a quadratic non-residue. We work with an odd prime p for most of this chapter.

Python Squares modulo a prime

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For each prime, exactly (p - 1)/2 residues and (p - 1)/2 non-residues appear. The reason: x² and (p - x)² are equal, so each residue has exactly two square roots, x and -x, and the p - 1 nonzero numbers fall into (p - 1)/2 pairs.

Euler's criterion

How can you test membership without listing all squares? Euler's criterion says that for an odd prime p and a not divisible by p:

a^((p-1)/2) ≡ 1 (mod p) if a is a residue, and ≡ -1 (mod p) if it is a non-residue.

Proof sketch: the polynomial x^((p-1)/2) - 1 has at most (p - 1)/2 roots modulo a prime. Each residue a = y² satisfies a^((p-1)/2) = y^(p-1) = 1 by Fermat, and there are already (p - 1)/2 residues, so those are exactly the roots. For the others, (a^((p-1)/2))² = a^(p-1) = 1, so the value is ±1, and it cannot be 1.

Python Euler's criterion versus the list of squares

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Euler's criterion costs one modular exponentiation, so it works even for a 127-bit prime. The only values that ever occur are 1 and p - 1, which is -1.

A multiplicative pattern

Write (a/p) for +1 if a is a residue and -1 if it is not (this is the Legendre symbol, the subject of the next lesson). Because the exponent in Euler's criterion distributes over products:

  • residue × residue = residue
  • residue × non-residue = non-residue
  • non-residue × non-residue = residue

That is the same sign rule as multiplying ±1. In group terms the residues form an index-2 subgroup of the multiplicative group modulo p. If g is a primitive root, the residues are exactly the even powers of g.

Python The sign rule and primitive roots

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The even powers of the primitive root coincide with the residue list, which is a handy way to see the pattern.

Square roots when p ≡ 3 (mod 4)

If a is a residue and p = 4k + 3, then r = a^((p+1)/4) mod p is a square root: r² = a^((p+1)/2) = a · a^((p-1)/2) = a · 1 = a. The other root is p - r. For primes of the form 4k + 1, we need a longer algorithm, Tonelli-Shanks.

Python Fast square roots for p = 3 mod 4

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Composite moduli

Modulo a composite n, things change. For squarefree n = p₁p₂...pₖ, an a coprime to n is a residue exactly when it is a residue modulo every pᵢ, and then it has 2^k square roots. That is the structure behind the Rabin cryptosystem: finding square roots modulo n = pq is as hard as factoring n.

Python Four square roots modulo n = p*q

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Every residue coprime to 77 has exactly 4 square roots, and 1 has the four roots 1, 34, 43 and 76. The two nontrivial roots (34 and 43) are the numbers that Miller-Rabin hunts for.

flowchart LR
    A["a mod p"] --> E["compute a^((p-1)/2) mod p"]
    E -->|"= 1"| R["residue: two roots r and p - r"]
    E -->|"= p - 1"| N["non-residue: no root"]
    E -->|"= 0"| Z["p divides a"]

Euler's criterion in one picture.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. How many quadratic residues are there among 1..p-1 for an odd prime p?

    x and p - x give the same square, so the p - 1 numbers collapse into (p - 1)/2 residues.
  2. 2. What does a^((p-1)/2) mod p equal when a is a non-residue?

    By Euler's criterion the value is -1 for non-residues.
  3. 3. For p = 11 and a = 5, what is a square root?

    44 = 16 = 5 mod 11, so 4 is a root (the other is 7). Also 33 = 9 which is not 5.
  4. 4. How many square roots does a unit residue have modulo n = pq with distinct odd primes?

    Two roots modulo each prime combine by the Chinese remainder theorem into 2*2 = 4 roots.

Summary

  • a is a quadratic residue mod p if x² ≡ a has a solution; exactly half of the nonzero residues are.
  • Euler's criterion: a^((p-1)/2) ≡ ±1, with +1 iff a is a residue.
  • Residue signs multiply like ±1; residues are the even powers of a primitive root.
  • For p ≡ 3 (mod 4) the roots of a are ±a^((p+1)/4).
  • Modulo n = pq each residue has four square roots, which links to factoring.

Next: Legendre and Jacobi Symbols