= Modular congruence
{title2=$\equiv$}
= Congruence modulo an integer
{synonym}
For <integers> $a,b$ and a positive <integer modulus> $n$, modular congruence means
$$
a\equiv b\pmod n\iff n\mid(a-b).
$$
Thus $a-b=kn$ for some <integer> $k$: the two <integers> differ by complete cycles of length $n$. For example, $14\equiv2\pmod{12}$ because $14-2=12$, and $-1\equiv11\pmod{12}$ because $-1-11=-12$. A <modular congruence> need not be an equality of <integers>.
On a twelve-position clock labelled $0,1,\ldots,11$, adding five to nine follows $9\to10\to11\to0\to1\to2$. Hence $9+5=14\equiv2\pmod{12}$: the final position remembers the <remainder> while forgetting a complete revolution.
\Image[/modular-clock-addition.png]
{title=Adding five to nine takes five clockwise steps and ends at two modulo twelve}
The same idea tracks any count repeating every $n$ steps. It also lets us compute sums and products with small <residue classes>, reducing intermediate results without changing the final class. The justification comes from <addition> and <multiplication> being well-defined on <residue classes>.
In \i[Disquisitiones arithmeticae] (1801), <Carl Friedrich Gauss> defines <modular congruence> by <divisibility> in article 1; article 2 describes the <integers> $a+kn$ and adopts $\equiv$. These passages document his presentation and notation, without claiming that repeating remainders began in 1801. https://la.wikisource.org/wiki/Disquisitiones_arithmeticae/Sectio_prima[Gauss, Disquisitiones arithmeticae, section I, articles 1–2; original text in the 1870 collected edition]{ref}
Back to article page
