Square b2 · Mathematics · Queenside

Congruence

Modular congruence: a and b agree modulo n.

Meaning

The congruence a≡b(modn)a\equiv b\pmod{n} means that nn divides the difference a−ba-b, written n∣(a−b)n\mid(a-b). Equivalently, aa and bb leave the same remainder when divided by the modulus nn (for n>0n>0). Congruence modulo nn is an equivalence relation on the integers, and the equivalence classes form the ring Z/nZ\mathbb{Z}/n\mathbb{Z} of integers modulo nn.

Arithmetic with congruences respects addition and multiplication: if a≡b(modn)a\equiv b\pmod{n} and c≡d(modn)c\equiv d\pmod{n}, then a+c≡b+d(modn)a+c\equiv b+d\pmod{n} and ac≡bd(modn)ac\equiv bd\pmod{n}. This is the formal content of “clock arithmetic” and of residual arithmetic in computation.

Context

Carl Friedrich Gauss introduced the notation a≡b(modn)a\equiv b\pmod{n} in the opening of Disquisitiones Arithmeticae (1801), giving modular arithmetic its modern language. The underlying idea—working with remainders—is ancient: the Chinese remainder theorem appears in the third-century Sunzi Suanjing; medieval Islamic and European calendrical calculations repeatedly reduce large counts modulo 77, 1919, or 6060.

Gauss made congruence a systematic tool. From it flow Euler’s theorem, Wilson’s theorem, the structure of the multiplicative group (Z/nZ)×(\mathbb{Z}/n\mathbb{Z})^{\times}, and the language in which quadratic reciprocity is stated. In the twentieth century, modular arithmetic became infrastructure for computer science: hashing, checksums, cyclic redundancy, and public-key cryptography (RSA, Diffie–Hellman) all compute extensively in Z/nZ\mathbb{Z}/n\mathbb{Z} or related rings.

Philosophically, congruence illustrates how mathematics studies structure up to a chosen indifference. Declaring aa and bb “the same mod nn” quotients away multiples of nn and reveals a finite arithmetic with nn residue classes. That move—forming quotients by equivalence relations—recurs in topology, algebra, and geometry.

On the Canon Board, congruence sits between zero and the binomial theorem as a bridge from elementary arithmetic to algebra proper: the first great example of a residue system, and the notation in which much of number theory is still written.

Congruence also clarifies the structure of cyclic phenomena: days of the week, musical pitch classes, and discrete rotations are all instances of Z/nZ\mathbb{Z}/n\mathbb{Z}. The Chinese remainder theorem decomposes Z/nZ\mathbb{Z}/n\mathbb{Z} when nn factors into coprime pieces, a structural fact used from calendar design to parallel computation. In that sense the modest notation a≡b(modn)a\equiv b\pmod{n} is the gateway to residual arithmetic as a full algebraic system.

Sources