Course contentsShow
← Mathematics
Lesson 2557 of 3,12151. Discrete Math — Sets, Relations, FunctionsFree lesson

Congruence Modulo n

Explore congruence modulo n as a fundamental example of an equivalence relation on integers.

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:

  1. Reflexive: Every integer a ≡ a (mod n) because n | (a - a) = 0
  2. Symmetric: If a ≡ b (mod n), then n | (a - b), which means n | (b - a), so b ≡ a (mod n)
  3. 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.