Congruence Modulo n
What You'll Learn
You'll learn how congruence modulo n defines one of the most important equivalence relations on the integers, partitioning them into neat, repeating cycles.
The Core Idea
Congruence modulo n is a relation on the integers that captures when two numbers have the same remainder after division by n.
We say two integers a and b are congruent modulo n (written a ≡ b (mod n)) if their difference is divisible by n. In other words:
a ≡ b (mod n) if and only if n | (a - b)
Equivalently, a and b leave the same remainder when divided by n.
Why It's an Equivalence Relation
Congruence modulo n satisfies all three properties:
- Reflexive: Every integer a ≡ a (mod n) because n | (a - a) = 0
- Symmetric: If a ≡ b (mod n), then n | (a - b), which means n | (b - a), so b ≡ a (mod n)
- Transitive: If a ≡ b (mod n) and b ≡ c (mod n), then n | (a - b) and n | (b - c), so n | [(a - b) + (b - c)] = (a - c), giving us a ≡ c (mod n)
The Partition It Creates
This equivalence relation partitions the integers into exactly n equivalence classes. For congruence modulo 5, for example:
- [0] = {..., -10, -5, 0, 5, 10, ...}
- [1] = {..., -9, -4, 1, 6, 11, ...}
- [2] = {..., -8, -3, 2, 7, 12, ...}
- [3] = {..., -7, -2, 3, 8, 13, ...}
- [4] = {..., -6, -1, 4, 9, 14, ...}
Think of it like a clock: modulo 12 creates the 12-hour cycle, where 13 o'clock and 1 o'clock are "the same."
Key Takeaway: Congruence modulo n is a fundamental equivalence relation that partitions the integers into n equivalence classes based on remainders, forming the foundation of modular arithmetic.