Equivalence Classes in Modular Arithmetic
What You'll Learn
You'll discover how congruence modulo n partitions all integers into distinct, non-overlapping groups called equivalence classes or residue classes.
The Core Idea
When you work with congruence modulo n, you're actually grouping integers by their remainders when divided by n. Each possible remainder (0, 1, 2, ..., n-1) defines an equivalence class—a collection of all integers that share that same remainder.
For example, modulo 5, every integer falls into exactly one of five equivalence classes:
- [0]: {..., -10, -5, 0, 5, 10, 15, ...} (all multiples of 5)
- [1]: {..., -9, -4, 1, 6, 11, 16, ...} (one more than multiples of 5)
- [2]: {..., -8, -3, 2, 7, 12, 17, ...}
- [3]: {..., -7, -2, 3, 8, 13, 18, ...}
- [4]: {..., -6, -1, 4, 9, 14, 19, ...}
Notice that 7 ≡ 12 (mod 5) because both belong to [2]—they differ by a multiple of 5.
Why This Matters
This partition is complete (every integer belongs to some class) and disjoint (no integer belongs to two different classes). This makes congruence an equivalence relation, satisfying:
- Reflexive: a ≡ a (mod n)
- Symmetric: if a ≡ b (mod n), then b ≡ a (mod n)
- Transitive: if a ≡ b and b ≡ c (mod n), then a ≡ c (mod n)
Think of it like sorting all integers into n labeled bins based on their "remainder fingerprint." Once sorted, you can do arithmetic by working with just the bin labels (0 through n-1) instead of the original huge numbers.
Key Takeaway: Congruence modulo n partitions the integers into n equivalence classes, each containing all numbers with the same remainder when divided by n, transforming infinite arithmetic into a finite system.