Modular arithmetic and invertible residues

Fix an integer modulus m at least two. Integers a and b are congruent modulo m if m divides their difference. The class containing a consists of a plus all integer multiples of m. Choosing a different representative changes the written integer but not its class. The usual representatives from zero through m − 1 are convenient, not mathematically privileged; negative representatives can simplify calculations considerably.

Addition and multiplication are well defined because replacing an input by a multiple of m changes the result by another multiple of m. For multiplication, expand the two replaced representatives and inspect each extra term. This is the reason that one may reduce intermediate products before they grow large. Equality of integers is stronger than congruence: 17 and 5 are not equal integers, although they represent the same class modulo 12.

A residue a is invertible when some integer u satisfies au congruent to one modulo m. Such a u exists exactly when gcd(a, m) is one. One direction follows because a common divisor would divide both au and m, and hence one. Conversely, a Bézout equation au + mv = 1 immediately supplies an inverse. The inverse is unique as a residue class, though it has infinitely many integer representatives.

Do not cancel a nonunit while keeping the same modulus. For example 2 × 1 and 2 × 4 are congruent modulo 6, but 1 and 4 are not. A general linear congruence ax congruent to b modulo m has solutions exactly when d = gcd(a, m) divides b. When m/d is greater than one, dividing a, b, and m by d gives an invertible reduced coefficient; the original modulus then contains d distinct lifted solutions. If d = m and d divides b, both original coefficients are zero modulo m, and every residue x is a solution; the reduced congruence modulo one is automatic.

A nonzero residue can multiply another nonzero residue to zero when the modulus is composite. Modulo six, two times three is zero. This does not contradict ordinary integer arithmetic; the result six belongs to the zero class. For a prime modulus every nonzero class is invertible, because no smaller positive representative shares a prime factor with the modulus. This is the basic reason prime-modulus arithmetic is especially regular.

Keep the object of a computation visible: a representative, a residue class, or an integer equation. If an application requires an actual range of values, a modular solution must be intersected with that range afterward. Efficient modular exponentiation similarly depends on reducing products, never on replacing an exponent without justification. Later exponent theorems will provide legitimate periods, but they require invertibility assumptions that cannot be inferred from the notation alone.