Congruence Definition

Number Theory · Axiom Academy

Understanding the formal definition of modular congruence in number theory Two integers a and b are said to be congruent modulo n if n divides their difference. In other words, a - b is a multiple of n , or equivalently, there exists an integer k such that a - b = kn . 2. Understanding Through Examples Let's explore the definition with concrete examples to build intuition. We check: Does 4 divide (17 - 5)? Since 17 - 5 = 12 = 4 × 3, yes! Therefore 17 ≡ 5 (mod 4) We check: Does 5 divide (23 - 8)? Since 23 - 8 = 15 = 5 × 3, yes! Therefore 23 ≡ 8 (mod 5) 3. Equivalence to Same Remainder The formal definition has a beautiful equivalent interpretation: a ≡ b (mod n) means a and b leave the same remainder when divided by n . a ≡ b (mod n) if and only if a and b have the same remainder when divided by n If a and b have the same remainder r when divided by n, we can write: a = q₁n + r for some integer q₁ b = q₂n + r for some integer q₂ Then: a - b = (q₁n + r) - (q₂n + r) = (q₁ - q₂)n This shows that n divides (a - b), confirming n | (a - b)!

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