Quadratic Residues

By SkytrailGroup Mathematics Editorial Team April 12, 2026

Definition

a is a QR mod p if x²≡a (mod p) has a solution. Legendre symbol: \(\left(\frac{{a}}{{p}}\right)=a^{{(p-1)/2}}\bmod p\in\{{0,\pm1\}}\).

Examples

Example 1. Is 2 a QR mod 7?

Solution. 2³=8≡1 (mod 7). Yes.

In Depth

An integer \(a\) is a quadratic residue modulo \(p\) (odd prime, \(p\nmid a\)) if \(x^2\equiv a\pmod{p}\) has a solution. There are exactly \((p-1)/2\) quadratic residues and \((p-1)/2\) non-residues among \(\{1,\ldots,p-1\}\).

The Legendre symbol \(\left(\frac{a}{p}\right)=a^{(p-1)/2}\bmod p\) equals \(+1\) if \(a\) is a QR, \(-1\) if a non-residue, and \(0\) if \(p\mid a\). It is completely multiplicative in \(a\) and is computed efficiently using Euler's criterion.

The law of quadratic reciprocity (Gauss): for distinct odd primes \(p,q\), \(\left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=(-1)^{\frac{p-1}{2}\cdot\frac{q-1}{2}}\). This means the two Legendre symbols agree unless both \(p\equiv q\equiv3\pmod4\). Gauss gave eight proofs; over 200 proofs are now known.

The Jacobi symbol \(\left(\frac{a}{n}\right)\) extends the Legendre symbol to composite \(n\) as a product of Legendre symbols over prime factors. It satisfies the same reciprocity law but \(\left(\frac{a}{n}\right)=1\) does not guarantee \(a\) is a QR mod \(n\).

Quadratic residues appear in: the Tonelli–Shanks algorithm for computing square roots mod \(p\); the quadratic sieve factoring algorithm; and the construction of Paley graphs and Hadamard matrices in combinatorics.

Key Properties & Applications

The Tonelli–Shanks algorithm computes \(\sqrt{a}\bmod p\) in \(O(\log^2 p)\) time. It factors \(p-1=2^s\cdot q\) (\(q\) odd) and uses the structure of the 2-Sylow subgroup of \((\mathbb{Z}/p\mathbb{Z})^*\). The Cipolla algorithm is an alternative with similar complexity.

Gauss sums \(g(\chi)=\sum_{a=0}^{p-1}\chi(a)e^{2\pi ia/p}\) for the Legendre symbol \(\chi=(\cdot/p)\) satisfy \(|g(\chi)|^2=p\). They are used to prove quadratic reciprocity and appear in the functional equation of Dirichlet \(L\)-functions.

Quadratic residues are used in the construction of Paley graphs: vertices are elements of \(\mathbb{F}_p\), with edges between \(x\) and \(y\) iff \(x-y\) is a nonzero QR. Paley graphs are self-complementary and have strong pseudorandom properties, making them useful in combinatorics and coding theory.