residueclass

A residue class modulo n, for a positive integer n, is the set of all integers that are congruent to a given integer a modulo n. Formally, it is the set {a + nk : k ∈ Z}. It is denoted [a]_n or a mod n. The residue class contains all integers that share the same remainder when divided by n.

The collection of all residue classes modulo n partitions the integers into n disjoint classes: [0]_n, [1]_n, ..., [n-1]_n. These classes form the quotient structure Z/nZ, equipped with addition and multiplication defined by [a]_n + [b]_n = [a+b]_n and [a]_n [b]_n = [ab]_n. This makes Z/nZ a finite ring; if n is prime, it is in fact a field.

Canonical representatives are commonly taken to be the least nonnegative residues in {0, 1, ..., n−1}, though any element of [a]_n serves as a valid representative. The defining relation is a ~ b if and only if n divides a − b, i.e., a ≡ b mod n.

Beyond integers, the concept generalizes to any ring R with an ideal I: the residue classes modulo I form the quotient ring R/I, used to study arithmetic modulo I in a broader context.

Residue classes are fundamental in number theory and its applications. They underpin solving congruences, the Chinese Remainder Theorem, and modular arithmetic computations used in cryptography and algorithms. For example, modulo 5, the residue class [3]_5 consists of {…, −7, −2, 3, 8, 13, …}, and [3]_5 = [8]_5.