Properties of Congruence Relations
What you'll learn: You'll discover the four fundamental properties that make congruence a well-behaved equivalence relation compatible with arithmetic.
The Core Idea
Congruence modulo n isn't just convenient notation—it behaves like equality in many ways. This lesson formalizes why modular arithmetic "just works" by examining four key properties: reflexivity, symmetry, transitivity, and compatibility with arithmetic operations.
Reflexivity
Any integer is congruent to itself: a ≡ a (mod n) for all integers a.
Why? Because a - a = 0, and n divides 0.
Symmetry
If a ≡ b (mod n), then b ≡ a (mod n).
Why? If n divides (a - b), then n also divides (b - a) = -(a - b).
Transitivity
If a ≡ b (mod n) and b ≡ c (mod n), then a ≡ c (mod n).
Why? If n divides (a - b) and (b - c), then n divides their sum (a - b) + (b - c) = (a - c).
These three properties make congruence an equivalence relation—it partitions integers into equivalence classes (the residue systems you've studied).
Compatibility with Arithmetic Operations
This is what makes congruence powerful for computation:
- Addition: If a ≡ b (mod n) and c ≡ d (mod n), then a + c ≡ b + d (mod n)
- Multiplication: If a ≡ b (mod n) and c ≡ d (mod n), then ac ≡ bd (mod n)
- Powers: If a ≡ b (mod n), then a^k ≡ b^k (mod n) for any positive integer k
Analogy: Think of congruence classes as "shapes" that remain unchanged under addition and multiplication—just like how adding two even numbers always gives an even number.
Key Takeaway: Congruence modulo n is an equivalence relation (reflexive, symmetric, transitive) that respects addition, multiplication, and exponentiation, making it a robust framework for modular arithmetic.