congruences

Congruences are a relation on integers that expresses that two numbers leave the same remainder after division by a fixed positive integer, the modulus. For integers a, b and a modulus n > 0, a ≡ b (mod n) if n divides a − b. Equivalently, a and b have the same remainder when divided by n. The relation partitions the integers into residue classes modulo n, often denoted [a] or a + nZ.

Arithmetic with congruences is well behaved: if a ≡ b (mod n) and c ≡ d (mod n), then a ± c ≡ b ± d (mod n) and a c ≡ b d (mod n). Hence addition, subtraction and multiplication descend to the set of residue classes modulo n. In particular, reduction modulo n allows every integer to be replaced by a unique representative in 0, 1, ..., n − 1.

Invertibility and linear congruences are central topics. An integer a has a multiplicative inverse modulo n if gcd(a, n) = 1; in this case there exists x with a x ≡ 1 (mod n). A linear congruence a x ≡ b (mod n) has solutions precisely when gcd(a, n) divides b. If solvable, the solution set consists of gcd(a, n) incongruent solutions modulo n.

The Chinese remainder theorem states that, for pairwise coprime moduli n1, ..., nk, the system x ≡ a_i (mod n_i) has a unique solution modulo N = n1…nk. Congruences underpin many areas of number theory and appear in algorithms for primality, cryptography, coding theory, and combinatorics.