Skip to content
Tutorials Center
My learning

Topics

Lesson 12 of 37 · Congruences

Congruences: The Basics

Learn congruence modulo n, its equivalence-class view, the rules for adding, subtracting and multiplying congruences, and why division needs care. With Python.

A clock shows 3 hours after 11 o'clock as 2, not 14, because it only keeps the remainder after dividing by 12. Gauss turned that everyday idea into a notation in 1801. We say that a is congruent to b modulo n, written

a ≡ b (mod n),

when n divides a − b. So 14 ≡ 2 (mod 12), because 12 | 12, and 7 ≡ −3 (mod 10), because 10 | 10. In Python, a % n == b % n tests exactly that.

Congruences let you ignore everything about an integer except its remainder, which makes huge computations manageable. This lesson sets out the definition and the rules; the following lessons solve equations and use the results.

Three equivalent ways to say it

For an integer n ≥ 2, the following statements about a and b mean the same thing.

  1. n | (a − b).
  2. a = b + kn for some integer k.
  3. a and b leave the same remainder when divided by n.
Python Test congruence three ways

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Congruence is an equivalence relation

For fixed n and any integers a, b, c:

  • Reflexive: a ≡ a.
  • Symmetric: if a ≡ b then b ≡ a.
  • Transitive: if a ≡ b and b ≡ c then a ≡ c.

So congruence mod n splits ℤ into n residue classes. The class of a is [a] = {..., a − n, a, a + n, a + 2n, ...}. For n = 5 the classes are [0], [1], [2], [3], [4], and every integer lies in exactly one. This is the "boxes by remainder" picture from the division algorithm.

Arithmetic of congruences

The reason congruences are useful is that they can be added and multiplied like equations.

Theorem. If a ≡ b and c ≡ d (mod n), then

  • a + c ≡ b + d (mod n),
  • a − c ≡ b − d (mod n),
  • a · c ≡ b · d (mod n),
  • aᵏ ≡ bᵏ (mod n) for every k ≥ 0.

Proof of the product rule. Write a = b + sn and c = d + tn. Then ac = bd + (bt + ds + stn)n, so ac − bd is a multiple of n. ∎

This means you can reduce at any moment. To find the last digit of 7¹⁰⁰, work mod 10: 7² = 49 ≡ 9 ≡ −1, so 7⁴ ≡ 1, and 7¹⁰⁰ = (7⁴)²⁵ ≡ 1. The last digit is 1.

Python Reduce early, reduce often

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Division is the tricky operation

You may add the same number to both sides of a congruence and multiply both sides by the same number. You may not always divide. For example 6 ≡ 12 (mod 6), but cancelling a 3 gives 2 ≡ 4 (mod 6), which is false.

The safe cancellation law: if ac ≡ bc (mod n) and gcd(c, n) = 1, then a ≡ b (mod n). More generally, if ac ≡ bc (mod n) and d = gcd(c, n), then a ≡ b (mod n/d). The proof uses Euclid's lemma ideas: n | c(a − b), and removing the part of n shared with c leaves n/d | (a − b).

Python When can we cancel?

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The cancellation works exactly for the c values that are coprime to n. This is the first sign of a deeper pattern: the numbers coprime to n form a nicer system than all residues.

Properties worth memorizing

  • If a ≡ b (mod n) and d | n, then a ≡ b (mod d). A statement mod 12 gives statements mod 2, 3, 4, 6.
  • If a ≡ b (mod m) and a ≡ b (mod n) then a ≡ b (mod lcm(m, n)). For coprime moduli that means mod mn.
  • Squares mod 4 are 0 or 1; cubes mod 9 are 0, 1 or 8; fourth powers mod 16 are 0 or 1.
Python Residue patterns of powers

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

These tiny tables make quick impossibility proofs. For example x² + y² = 4k + 3 has no integer solutions, because squares are 0 or 1 mod 4, so x² + y² can only be 0, 1 or 2 mod 4.

flowchart LR
  Z["All integers"] --> R0["[0] mod 5"]
  Z --> R1["[1] mod 5"]
  Z --> R2["[2] mod 5"]
  Z --> R3["[3] mod 5"]
  Z --> R4["[4] mod 5"]

Congruence mod 5 cuts the integers into five classes.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. Which statement is true?

    17 - 2 = 15 is divisible by 5.
  2. 2. What is the last digit of 3^2025?

    3 has the cycle 3, 9, 7, 1 modulo 10 and 2025 = 4 * 506 + 1, so the digit is 3.
  3. 3. 6 = 12 (mod 6) is true. Why is it wrong to conclude 2 = 4 (mod 6) by cancelling 3?

    You may cancel c only when gcd(c, n) = 1; otherwise the modulus becomes n / gcd(c, n).
  4. 4. If a = b (mod n) and c = d (mod n), which is always true?

    Congruences may be added, subtracted and multiplied; division and exponents with congruent exponents are not safe.

Summary

  • a ≡ b (mod n) means n | (a − b), equivalently a and b have the same remainder mod n.
  • Congruence mod n is an equivalence relation that splits ℤ into n residue classes.
  • Congruences can be added, subtracted, multiplied and raised to powers, so you can reduce at every step.
  • Cancelling c is safe only if gcd(c, n) = 1; otherwise the modulus shrinks to n / gcd(c, n).
  • Small residue tables prove that some equations have no integer solutions.

Next: Linear Congruences