Mathwords logoMathwords

Quadratic Residue — Definition, Formula & Examples

A quadratic residue modulo nn is an integer aa for which the equation x2≡a(modn)x^2 \equiv a \pmod{n} has a solution. In other words, aa is a quadratic residue mod nn if some integer squared gives aa when you divide by nn and take the remainder.

Let nn be a positive integer and aa an integer with gcd⁡(a,n)=1\gcd(a, n) = 1. Then aa is called a quadratic residue modulo nn if there exists an integer xx such that x2≡a(modn)x^2 \equiv a \pmod{n}. If no such xx exists, aa is called a quadratic nonresidue modulo nn.

Key Formula

a(p−1)/2≡{1(modp)if a is a quadratic residue mod p−1(modp)if a is a quadratic nonresidue mod pa^{(p-1)/2} \equiv \begin{cases} 1 \pmod{p} & \text{if } a \text{ is a quadratic residue mod } p \\ -1 \pmod{p} & \text{if } a \text{ is a quadratic nonresidue mod } p \end{cases}
Where:
  • aa = An integer not divisible by p
  • pp = An odd prime

How It Works

To check whether aa is a quadratic residue mod nn, compute x2 mod nx^2 \bmod n for each xx from 00 to n−1n-1 and see if aa appears among the results. For an odd prime pp, exactly (p−1)/2(p-1)/2 of the integers 1,2,…,p−11, 2, \ldots, p-1 are quadratic residues. Euler's criterion provides a shortcut when pp is prime: aa is a quadratic residue mod pp if and only if a(p−1)/2≡1(modp)a^{(p-1)/2} \equiv 1 \pmod{p}. The Legendre symbol (ap)\left(\frac{a}{p}\right) encodes this classification, equaling +1+1 for residues and −1-1 for nonresidues.

Worked Example

Problem: Determine all quadratic residues modulo 7.
Compute squares: Square each integer from 1 to 6 and reduce modulo 7.
12≡1,22≡4,32≡2,42≡2,52≡4,62≡1(mod7)1^2 \equiv 1,\quad 2^2 \equiv 4,\quad 3^2 \equiv 2,\quad 4^2 \equiv 2,\quad 5^2 \equiv 4,\quad 6^2 \equiv 1 \pmod{7}
Collect distinct results: The distinct values obtained are 1, 2, and 4. These are the quadratic residues mod 7. Notice there are exactly (7−1)/2 = 3 of them.
Identify nonresidues: The remaining values 3, 5, and 6 are quadratic nonresidues mod 7, since no square produces them.
Answer: The quadratic residues modulo 7 are {1,2,4}\{1, 2, 4\}, and the quadratic nonresidues are {3,5,6}\{3, 5, 6\}.

Why It Matters

Quadratic residues are central to the law of quadratic reciprocity, one of the landmark theorems in number theory. They also underpin modern cryptographic protocols such as the Goldwasser–Micali encryption scheme, where security relies on the difficulty of distinguishing residues from nonresidues modulo a large composite number.

Common Mistakes

Mistake: Including 0 as a quadratic residue when working modulo a prime p.
Correction: By convention, quadratic residues are drawn from integers coprime to the modulus. Since gcd⁡(0,p)=p≠1\gcd(0, p) = p \neq 1, zero is excluded from the classification.