Complete and Reduced Residue Systems
What you'll learn: You'll discover how to build two fundamental sets of representatives for modular arithmetic: one that covers all residues, and one that only includes those coprime to your modulus.
The Core Idea
When working modulo n, every integer falls into one of n equivalence classes. A complete residue system modulo n is simply a set containing exactly one representative from each of these classes.
Think of it like choosing ambassadors: you need exactly one person from each country at the table—no duplicates, no absences.
The most natural complete residue system is {0, 1, 2, ..., n−1}, but {1, 2, 3, ..., n} or even {−5, 3, 10, 17, 24, ...} could work too (for n = 5), as long as you hit each residue class exactly once.
Reduced Residue Systems
Not all residues are created equal. Sometimes we only care about the units—numbers that have multiplicative inverses modulo n. These are precisely the integers coprime to n (i.e., gcd(a, n) = 1).
A reduced residue system modulo n contains exactly one representative from each equivalence class of units modulo n.
Example: For n = 8, the complete residue system is {0, 1, 2, 3, 4, 5, 6, 7}.
But only {1, 3, 5, 7} are coprime to 8, so {1, 3, 5, 7} is a reduced residue system modulo 8.
The number of elements in a reduced residue system is φ(n), Euler's totient function—but we're not diving into that yet!
Key Takeaway: A complete residue system modulo n has exactly n representatives covering all equivalence classes; a reduced residue system contains only those coprime to n, representing the units in modular arithmetic.