Course contentsShow
← Mathematics
Lesson 2731 of 3,12154. Number TheoryFree lesson

Equivalence Classes in Modular Arithmetic

Understand congruence as an equivalence relation that partitions integers into residue classes.

Equivalence Classes in Modular Arithmetic

What You'll Learn

You'll discover how congruence modulo n partitions all integers into distinct, non-overlapping groups called equivalence classes or residue classes.

The Core Idea

When you work with congruence modulo n, you're actually grouping integers by their remainders when divided by n. Each possible remainder (0, 1, 2, ..., n-1) defines an equivalence class—a collection of all integers that share that same remainder.

For example, modulo 5, every integer falls into exactly one of five equivalence classes:

  • [0]: {..., -10, -5, 0, 5, 10, 15, ...} (all multiples of 5)
  • [1]: {..., -9, -4, 1, 6, 11, 16, ...} (one more than multiples of 5)
  • [2]: {..., -8, -3, 2, 7, 12, 17, ...}
  • [3]: {..., -7, -2, 3, 8, 13, 18, ...}
  • [4]: {..., -6, -1, 4, 9, 14, 19, ...}

Notice that 7 ≡ 12 (mod 5) because both belong to [2]—they differ by a multiple of 5.

Why This Matters

This partition is complete (every integer belongs to some class) and disjoint (no integer belongs to two different classes). This makes congruence an equivalence relation, satisfying:

  • Reflexive: a ≡ a (mod n)
  • Symmetric: if a ≡ b (mod n), then b ≡ a (mod n)
  • Transitive: if a ≡ b and b ≡ c (mod n), then a ≡ c (mod n)

Think of it like sorting all integers into n labeled bins based on their "remainder fingerprint." Once sorted, you can do arithmetic by working with just the bin labels (0 through n-1) instead of the original huge numbers.

Key Takeaway: Congruence modulo n partitions the integers into n equivalence classes, each containing all numbers with the same remainder when divided by n, transforming infinite arithmetic into a finite system.