Properties of Congruences

Number Theory · Axiom Academy

LESSON Properties of Congruences Understanding the fundamental properties that govern modular arithmetic 1. Equivalence Relation Properties Congruence modulo n is an equivalence relation , meaning it satisfies three fundamental properties: reflexive, symmetric, and transitive. 2. Proofs of Equivalence Properties Let's prove each property using the definition of congruence. Proof: We need to show that n | (a - a). Since a - a = 0 and n | 0 for any n, we have: Proof: If a is congruent to b mod n, then n | (a - b). This means a - b = kn for some integer k. Therefore, b - a = -kn = (-k)n, and since -k is also an integer, n | (b - a). 3. Proof of Transitive Property Proof: From the given conditions: Since a is congruent to b mod n, we have n | (a - b), so a - b = k₁n for some integer k₁. Since b is congruent to c mod n, we have n | (b - c), so b - c = k₂n for some integer k₂. Since k₁ + k₂ is an integer, n | (a - c). Indeed: 17 - 7 = 10 = 2(5), so 17 is congruent to 7 mod 5. Congruences can be added together, just like equations. Given: a is congruent to b mod n and c is congruent to d mod n. This means n | (a - b) and n | (c - d). So a - b = k₁n and c - d = k₂n for some integers k₁, k₂. Since k₁ + k₂ is an integer, n | ((a + c) - (b + d)). Verification: 23 + 19 = 42, and 2 + 5 = 7. Indeed, 42 is congruent to 7 mod 7 (both leave remainder 0). 5. Subtraction and Multiplication Properties Proof follows directly from the addition property (add the negatives).

This is the written version of the interactive lesson above. See the full Number Theory course.