A clock reads $11$. Five hours later it reads $4$, not $16$. This is not a failure of arithmetic; it is a change in the question. We have stopped asking for equality of integers and started asking whether two integers have the same remainder after division by $12$. Congruence is the language that makes this shift precise.

The same pattern appears whenever an infinite arithmetic problem has a finite shadow. To decide whether an integer is even, we do not need the integer itself; its remainder modulo $2$ is enough. To study the last digit of a power, we reduce modulo $10$. To solve a Diophantine equation, we first ask whether it has any solution after reducing modulo a carefully chosen integer. Congruence turns divisibility into an [equivalence relation](/page/Equivalence%20Relation), and the resulting arithmetic of residue classes is the entry point to modular arithmetic, finite rings, and much of elementary number theory.

[example: A Clock Calculation] Suppose a clock has $12$ positions and currently shows $11$. After $5$ hours, the integer count is \begin{align*} 11+5=16. \end{align*} To convert this integer count back to a clock position, divide by $12$: \begin{align*} 16=1\cdot 12+4. \end{align*} The remainder is $4$, so the clock shows $4$. This does not mean that $16=4$ as integers. Instead, \begin{align*} 16-4=12. \end{align*} Since $12=1\cdot 12$, the difference between $16$ and $4$ is a multiple of the modulus $12$. The clock keeps exactly the information that remains after multiples of $12$ are ignored. [/example]

The clock example also warns us against a common mistake. Congruence is not approximate equality. It is exact equality after a chosen loss of information. The modulus records precisely what information has been discarded, and the rest of the theory studies which parts of ordinary arithmetic survive that loss.

## Definition

Before we can calculate with remainders, we need a relation that records when two integers produce the same remainder. Divisibility provides the right test because two integers have the same remainder modulo $n$ exactly when their difference is divisible by $n$. Throughout this page, a modulus is a positive integer $n \in \mathbb{N}$.

[definition: Congruence Modulo $n$] Let $n \in \mathbb{N}$. For $a,b \in \mathbb{Z}$, we say that $a$ is congruent to $b$ modulo $n$, and write \begin{align*} a &\equiv b \pmod{n}, \end{align*} if \begin{align*} n &\mid (a-b). \end{align*} [/definition]

The integer $n$ is called the modulus. The case $n=1$ collapses all integers into a single congruence class, since every integer is divisible by $1$. For most arithmetic applications, the useful moduli are $n\geq 2$, where congruence keeps some information and discards the rest.

The definition is phrased using divisibility rather than remainders because divisibility behaves well under addition, subtraction, and multiplication. Remainders are useful for computation; divisibility is better for structure.

[example: Same Remainder, Same Congruence] Modulo $7$, the integers $31$ and $10$ have difference \begin{align*} 31-10 = 21. \end{align*} Since \begin{align*} 21 = 3\cdot 7, \end{align*} the integer $7$ divides $31-10$. By the definition of congruence modulo $7$, this gives \begin{align*} 31 \equiv 10 \pmod{7}. \end{align*} The same conclusion appears from division with remainder. We have \begin{align*} 31 = 4\cdot 7+3 \end{align*} and \begin{align*} 10 = 1\cdot 7+3. \end{align*} Both integers leave remainder $3$ after division by $7$, so they determine the same residue class modulo $7$. By contrast, \begin{align*} 31-11 = 20. \end{align*} The multiples of $7$ nearest to $20$ are \begin{align*} 2\cdot 7 = 14 \end{align*} and \begin{align*} 3\cdot 7 = 21. \end{align*} Thus $20$ is not a multiple of $7$, so $7\nmid 20$, and therefore \begin{align*} 31 \not\equiv 11 \pmod{7}. \end{align*} The test is exact: modulo $7$, sameness means that the difference is a multiple of $7$. [/example]

The definition gives a test for sameness modulo $n$, but it still needs structural justification. If congruence is going to support arithmetic on classes, then its classes must not overlap ambiguously. The next question is whether congruence behaves like an honest equivalence relation; this requires reflexivity, symmetry, and transitivity.

[quotetheorem:9332]

This theorem justifies the language of classes. Reflexivity says every integer belongs to its own class, symmetry says the order of comparison does not matter, and transitivity says the classes do not overlap in an inconsistent way. To compute with those classes, we also need a canonical way to name each one; this is supplied by division with remainder.

[quotetheorem:9333]

The theorem explains why modular arithmetic is finite: although each residue class contains infinitely many integers, exactly one representative lies in the standard range from $0$ to $n-1$. This finite list of representatives is the computational face of congruence.

## Residue Classes and Representatives

The equivalence-relation theorem says that congruence partitions the integers. To use that partition, we need a name for one piece of it: all integers that are indistinguishable from a chosen integer modulo $n$.

[definition: Residue Class Modulo $n$] Let $n \in \mathbb{N}$ and let $a \in \mathbb{Z}$. The residue class of $a$ modulo $n$ is \begin{align*} \bar{a} &= \{b \in \mathbb{Z}: b \equiv a \pmod{n}\}. \end{align*} [/definition]

A residue class is an infinite subset of $\mathbb{Z}$, but modulo $n$ there are only $n$ distinct classes. For example, modulo $5$ every integer belongs to exactly one of $\bar{0},\bar{1},\bar{2},\bar{3},\bar{4}$. The class is the object; the representative is only a convenient name for it.

To do arithmetic with residue classes, we need the collection of all classes. This construction is the finite arithmetic universe obtained by declaring multiples of $n$ to be invisible.