Congruences: When Different Numbers Are the Same

In mod 7, the numbers 3, 10, 17, and -4 are all the same thing.

They're different as integers. But in modular arithmetic, they behave identically. They all leave remainder 3 when divided by 7. Any calculation you do with one, you could do with another and get the same result (mod 7).

Congruent numbers are interchangeable in modular arithmetic.

That's the unlock. The symbol a ≡ b (mod n) means "a and b are the same, as far as mod n is concerned." They might look different, but arithmetically they're twins. This equivalence is what lets you replace big numbers with small remainders — and why modular arithmetic works at all.

The Definition, Again

a ≡ b (mod n) means:

• a and b leave the same remainder when divided by n
• n divides (a - b)
• a = b + kn for some integer k

All three definitions are equivalent.

17 ≡ 3 (mod 7) because:

• 17 = 2×7 + 3, 3 = 0×7 + 3 (same remainder 3)
• 7 | (17 - 3) = 14 ✓
• 17 = 3 + 2(7) ✓

Congruence Is an Equivalence Relation

Reflexive: a ≡ a (mod n) for all a.

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).

These properties mean congruence partitions the integers into equivalence classes.

Mod 5, the classes are:

• {..., -10, -5, 0, 5, 10, ...} — all ≡ 0
• {..., -9, -4, 1, 6, 11, ...} — all ≡ 1
• {..., -8, -3, 2, 7, 12, ...} — all ≡ 2
• {..., -7, -2, 3, 8, 13, ...} — all ≡ 3
• {..., -6, -1, 4, 9, 14, ...} — all ≡ 4

Every integer belongs to exactly one class.

Arithmetic Respects Congruence

If a ≡ a' and b ≡ b' (mod n), then:

Addition: a + b ≡ a' + b' (mod n) Subtraction: a - b ≡ a' - b' (mod n) Multiplication: ab ≡ a'b' (mod n) Powers: aᵏ ≡ (a')ᵏ (mod n)

You can substitute congruent values anywhere. That's why we can reduce numbers before computing.

Solving Congruences

Linear congruence: ax ≡ b (mod n)

Solution exists iff gcd(a, n) | b.

If gcd(a, n) = 1, there's a unique solution mod n.

Example: 3x ≡ 5 (mod 7)

gcd(3, 7) = 1, so a unique solution exists. Find 3⁻¹ mod 7: 3 × 5 = 15 ≡ 1 (mod 7), so 3⁻¹ ≡ 5. x ≡ 5 × 5 = 25 ≡ 4 (mod 7). Check: 3 × 4 = 12 ≡ 5 (mod 7) ✓

When No Solution Exists

2x ≡ 3 (mod 6)

gcd(2, 6) = 2. Does 2 | 3? No.

No solution. The left side is always even (mod 6), but 3 is odd.

When Multiple Solutions Exist

2x ≡ 4 (mod 6)

gcd(2, 6) = 2. Does 2 | 4? Yes.

Divide everything by 2: x ≡ 2 (mod 3).

Solutions mod 6: x = 2 or x = 5. Check: 2(2) = 4 ✓, 2(5) = 10 ≡ 4 ✓

Number of solutions = gcd(a, n) when solutions exist.

Systems of Congruences

Solve simultaneously: x ≡ 2 (mod 3) x ≡ 3 (mod 5)

By the Chinese Remainder Theorem, since gcd(3, 5) = 1, a unique solution exists mod 15.

Testing: x = 8 satisfies both. Check: 8 = 2×3 + 2 ≡ 2 (mod 3) ✓, 8 = 1×5 + 3 ≡ 3 (mod 5) ✓

Cancellation in Congruences

Caution: You can't always cancel.

6 × 2 ≡ 6 × 5 (mod 9) — both are 12 ≡ 3.

But 2 ≢ 5 (mod 9).

Safe cancellation: If gcd(c, n) = 1, then ca ≡ cb (mod n) implies a ≡ b (mod n).

Polynomial Congruences

x² ≡ 1 (mod 8)

Try all residues 0, 1, 2, ..., 7:

• 0² = 0 ≢ 1
• 1² = 1 ≡ 1 ✓
• 2² = 4 ≢ 1
• 3² = 9 ≡ 1 ✓
• 4² = 16 ≡ 0 ≢ 1
• 5² = 25 ≡ 1 ✓
• 6² = 36 ≡ 4 ≢ 1
• 7² = 49 ≡ 1 ✓

Solutions: x ≡ 1, 3, 5, 7 (mod 8).

Four solutions! Polynomial congruences can have more solutions than the degree suggests.

Wilson's Theorem

(p - 1)! ≡ -1 (mod p) for prime p.

Check: (7 - 1)! = 720. 720 = 102 × 7 + 6 = 102 × 7 + (-1) (mod 7). 720 ≡ -1 (mod 7) ✓

This provides a primality test (theoretically — too slow in practice).

Quadratic Residues

a is a quadratic residue mod n if x² ≡ a (mod n) has a solution.

Mod 7: 1² = 1, 2² = 4, 3² = 2 (since 9 = 7 + 2).

Quadratic residues mod 7: {1, 2, 4}. Non-residues: {3, 5, 6}.

This is the beginning of deeper number theory (quadratic reciprocity, Legendre symbols).

The Core Insight

Congruence treats infinitely many numbers as one.

All integers that share a remainder form an equivalence class. Within modular arithmetic, they're indistinguishable — you can swap them freely.

This collapse from infinite to finite is what makes modular arithmetic computationally powerful and theoretically rich. The structure of congruences reveals patterns invisible in ordinary arithmetic.

Part 8 of the Number Theory series.

Previous: Modular Arithmetic: Clock Math and Remainders Next: Fermat's Little Theorem: A Shortcut for Big Powers