Quadratic Residues

Summary: A quadratic residue modulo $d$ is a remainder that can arise when a perfect square is divided by $d$; Euler uses residue tables to prove that certain two-term formulas $a{t}^2+b{u}^2$ can never be perfect squares.

Sources: chapter-2.0.5

Last updated: 2026-05-08

---

Definition

An integer $r$ is a quadratic residue mod $d$ if there exists an integer $x$ such that $x^2\equiv r(\mathrm{mod}d)$. The set of all quadratic residues mod $d$ is a proper subset of $\{0,1,\dots ,d-1\}$.

If a number $N$ is a perfect square, then $N\mathrm{mod}d$ must be a quadratic residue. Conversely, if $N\mathrm{mod}d$ is not a quadratic residue, then $N$ cannot be a square.

---

Residue Tables

Mod 3

Every integer belongs to $3n$, $3n+1$, or $3n+2$.

Class	Square mod 3
$3n$	$0$
$3n+1$	$1$
$3n+2$	$1$

Quadratic residues mod 3: $\{0,1\}$. Residue $2$ is impossible.

Mod 4 and Mod 8

Class	Square mod 16
$4n$	$0$
$4n+1$	$1(\mathrm{mod}8)$
$4n+2$	$4(\mathrm{mod}16)$
$4n+3$	$1(\mathrm{mod}8)$

Even squares: only $16n$ or $16n+4$. Odd squares: all $\equiv 1(\mathrm{mod}8)$.

Impossible residues mod 8: $3$, $5$, $7$. Impossible even residues mod 16: $2$, $6$, $8$, $10$, $12$, $14$.

Mod 5

Class	Square mod 5
$5n$	$0$
$5n\pm 1$	$1$
$5n\pm 2$	$4$

Quadratic residues mod 5: $\{0,1,4\}$. Residues $2$ and $3$ are impossible.

Mod 7

Class	Square mod 7
$7n$	$0$
$7n\pm 1$	$1$
$7n\pm 2$	$4$
$7n\pm 3$	$2$

Quadratic residues mod 7: $\{0,1,2,4\}$. Residues $3$, $5$, $6$ are impossible.

General Divisor $d$ (§77)

The classes $dn+a$ and $dn-a$ give the same square remainder $a^2\mathrm{mod}d$. So the distinct non-zero square residues mod $d$ are $\{1^2,2^2,\dots ,\lfloor d/2{\rfloor }^2\}\mathrm{mod}d$.

---

Impossibility Test for $a{t}^2+b{u}^2$

To show $a{t}^2+b{u}^2$ is never a square, pick a modulus $d$ and check:

1. Compute all possible residues of $a{t}^2\mathrm{mod}d$ and $b{u}^2\mathrm{mod}d$.
2. Check that every possible sum $a{t}^2+b{u}^2\mathrm{mod}d$ falls outside the quadratic residues mod $d$.

Examples from Euler:

Formula	Modulus	Residues of sum	Verdict
$3t^2+2u^2$	$3$	$\{0+2,0+2,\dots \}=\{2\}$ (if $3\nmid u$)	Never square
$3t^2+2u^2$	$8$	$\{3+2,3+2\}=\{5\}$ (both odd)	Never square
$5t^2+2u^2$	$5$	$\{0+2,0+3\}$ (two subcases)	Never square
$7t^2+3u^2$	$7$	$\{0+3,0+6,0+5\}$, none in $\{0,1,2,4\}$	Never square

The general criterion (§74): $(4m+3)t^2+(4n+3)u^2$ is never a square for any integers $m$, $n$, because both coefficients are $\equiv 3(\mathrm{mod}4)$.

---

Historical Note

Euler’s treatment in Chapter V of Part II is an early systematic use of what later became the theory of quadratic residues. The full theory was developed by Gauss in the Disquisitiones Arithmeticae (1801), including the quadratic reciprocity law. Euler’s residue tables are a computational precursor.

---

Related pages

• ch2.0.5-impossibility-quadratic-squares
• ch2.0.6-integer-solutions-quadratic-squares
• pell-equation
• indeterminate-analysis
• prime-numbers