1
Congruence is an equivalence relation
Reflexive, symmetric, transitive — so it partitions ℤ into m classes, one per remainder.
Lesson · Number Theory and Cryptography · Congruences
Modular Arithmetic
a ≡ b (mod m) when m | (a − b). Congruence is an equivalence relation, addition and multiplication respect it, and cancellation is where it stops behaving like ordinary arithmetic.
a ≡ b (mod m) ⟺ m | (a − b)
congruences ADD and MULTIPLY like equations
CANCELLATION FAILS: 2·3 ≡ 2·8 (mod 10) but 3 ≢ 8
cancel a only when gcd(a, m) = 1
Almost ordinary arithmetic
Core ideas
What this lesson establishes
Congruence is Sets, Relations, and Functions's equivalence relation applied to the integers, and the classes support arithmetic.
2
Addition and multiplication are well defined
The result's class depends only on the inputs' classes, which is what makes arithmetic on classes legitimate.
3
Cancellation needs coprimality
ac ≡ bc (mod m) gives a ≡ b only when gcd(c, m) = 1. This is the one familiar rule that fails.
The material
Congruence
The definition, the well-definedness proof, and the rule that fails.
Definition · Congruence
For m > 0, a ≡ b (mod m) means m | (a − b); equivalently, a and b leave the same remainder on division by m.
Theorem · Congruence is an equivalence relation
It is reflexive (m | 0), symmetric (m | (a−b) gives m | (b−a)) and transitive (m | (a−b) and m | (b−c) give m | (a−c) by the linear-combination property).
By “Equivalence Relations and Partitions” in Sets, Relations, and Functions it therefore partitions ℤ into equivalence classes. There are exactly m of them, one for each remainder 0, 1, …, m−1, and the set of classes is written ℤ/mℤ or ℤ_m.
Theorem · Arithmetic is well defined
If a ≡ b (mod m) and c ≡ d (mod m), then a + c ≡ b + d and ac ≡ bd (mod m).
Write a = b + ms and c = d + mt. Then a + c = (b + d) + m(s + t), so the sums are congruent.
And ac = (b + ms)(d + mt) = bd + m(bt + ds + mst), so the products are congruent.
□
This is the well-definedness check “Functions” in Sets, Relations, and Functions warned about, carried out. It says arithmetic on classes is legitimate: the answer does not depend on which representatives were used, so [3] + [4] = [7] is a statement about classes rather than about the numbers 3 and 4.
The practical consequence is that a computation may be reduced at any point. To find 17 · 23 (mod 5), reduce first: 2 · 3 = 6 ≡ 1, rather than computing 391 and dividing.
Where it stops being ordinary arithmetic
Example · Cancellation fails
2 · 3 = 6 ≡ 16 = 2 · 8 (mod 10), and yet 3 ≢ 8 (mod 10). The factor 2 cannot be cancelled because gcd(2, 10) = 2 ≠ 1.
Theorem · Cancellation law
If ac ≡ bc (mod m) and gcd(c, m) = 1, then a ≡ b (mod m).
gcd(c,m) = 1 gives an inverse c⁻¹ by “Bézout's Identity and Modular Inverses”. Multiplying both sides by it leaves a ≡ b.
□
Example · Zero divisors
2 · 5 = 10 ≡ 0 (mod 10) with neither factor zero. In ℤ_10 there are nonzero elements whose product is zero — impossible in ℤ, and the reason ℤ_10 is not a field.
Theorem · Prime moduli behave best
ℤ_p for prime p has no zero divisors and every nonzero element has an inverse: it is a field. For composite m, exactly the elements coprime to m are invertible, and there are φ(m) of them.
Casting out nines
Example · A check on arithmetic
Since 10 ≡ 1 (mod 9), any number is congruent mod 9 to its digit sum. To check 4321 × 5678 = 24 534 638: digit sums are 10 ≡ 1 and 26 ≡ 8, product 8; the claimed answer has digit sum 35 ≡ 8. Consistent — and the check would catch most single digit errors, though not a transposition.
Interactive
Number theory workbench
Algorithms with their traces
Method
Computing modulo m
Reduce early and often.
1
Reduce the inputs first
17 · 23 (mod 5) is 2 · 3 (mod 5). Well-definedness is what makes this legitimate and it keeps the numbers small.
2
Add and multiply freely
Both operations respect congruence. Subtraction too, since it is addition of a negative.
3
Do not cancel without checking the gcd
ac ≡ bc gives a ≡ b only when gcd(c,m) = 1. This is the rule that catches people.
4
Reduce the final answer into [0, m)
Add m if the result is negative. Conventional representatives make answers comparable.
Modular arithmetic
Score 0 / 0Choose the answer you can justify.
The last digit of 7¹⁰⁰
That is 7¹⁰⁰ mod 10, and the powers cycle.
7¹ ≡ 7 7² ≡ 49 ≡ 9 7³ ≡ 63 ≡ 3 7⁴ ≡ 21 ≡ 1 (mod 10)
The powers cycle with period 4: 7, 9, 3, 1, 7, 9, 3, 1, …
100 = 4 · 25, so 7¹⁰⁰ = (7⁴)²⁵ ≡ 1²⁵ = 1 (mod 10)
The last digit of 7¹⁰⁰ is 1.
7¹⁰⁰ has 85 digits. We found its last one with four multiplications
and a division.
The cycle length 4 is not a coincidence: φ(10) = 4, and Euler's theorem in “Fermat's Little Theorem and Euler's Theorem” guarantees 7^{φ(10)} ≡ 1 whenever gcd(7,10) = 1. “Modular Exponentiation” turns this into a general algorithm.
Common mistakes
1
Cancelling a common factor without checking the gcdThe one familiar rule that fails. 2·3 ≡ 2·8 (mod 10) with 3 ≢ 8.
2
Reducing exponents modulo ma^b (mod m) does not let you reduce b mod m. Exponents reduce modulo φ(m), which is “Fermat's Little Theorem and Euler's Theorem”.
3
Leaving negative representativesCorrect but unconventional. Add m to land in [0, m).
Check your understanding
✓
Finish when you reduce before multiplying, automatically.
Compute 123 · 456 (mod 7) by reducing each factor first. Two small multiplications rather than one large one, and the answer is the same because congruence respects multiplication.
Note: Modular arithmetic is the arithmetic of ℤ/mℤ, the quotient of the integers by an equivalence relation. “Equivalence Relations and Partitions” in Sets, Relations, and Functions built exactly that structure; this course computes in it.