gen-define-congruence-relations-and-give-one-short-worked-exampl-12a9

Define congruence relations and give one short worked example.

# Congruence Relations ## Definition A **congruence relation** on an algebraic structure is an equivalence relation that is compatible with the operations of that structure. Formally, a relation ~ on a set S with binary operation * is a congruence relation if: 1. **Equivalence relation**: ~ is reflexive, symmetric, and transitive 2. **Compatibility**: If a ~ b and c ~ d, then (a * c) ~ (b * d) ## Worked Example **Congruence modulo n on integers** Define a ~ b if n | (a - b), written as a ≡ b (mod n). Let's verify **congruence mod 5** is a congruence relation on (ℤ, +): **Check compatibility with addition:** - Suppose 17 ≡ 2 (mod 5) and 23 ≡ 3 (mod 5) - We need: (17 + 23) ≡ (2 + 3) (mod 5) - Left side: 40 ≡ 0 (mod 5) ✓ - Right side: 5 ≡ 0 (mod 5) ✓ - Indeed 40 ≡ 5 (mod 5) since 5 | (40 - 5) = 35 **General proof:** If a ≡ b (mod n) and c ≡ d (mod n), then: - n | (a - b) and n | (c - d) - So n | [(a - b) + (c - d)] = [(a + c) - (b + d)] - Therefore (a + c) ≡ (b + d) (mod n) ✓ This compatibility is why modular arithmetic "works" and why we can form quotient structures like ℤ/nℤ.