Section 26

Modular arithmetic

intermediateviz

a \equiv b (mod n) ⟺ n ∣ (a - b)

Defines equality of remainders modulo n.

intermediateviz

a \equiv b, c \equiv d (mod n) \Rightarrow a + c \equiv b + d, a c \equiv b d (mod n)

Congruences are preserved under addition and multiplication.

intermediateviz

a a^{- 1} \equiv 1 (mod n) ⟺ g cd (a, n) = 1

The inverse exists exactly when a and n are coprime.

intermediate

a x + b y = g cd (a, b)

Connects the greatest common divisor with integer linear combinations.

advancedviz

x \equiv a_{i} (mod n_{i}); N = i \prod n_{i}

Systems with pairwise coprime moduli have a unique solution modulo N.

advancedviz

a^{p - 1} \equiv 1 (mod p) (p ∤ a)

Central result for modular arithmetic and cryptography.