Congruences
A congruence a ≡ b (mod m) means a and b leave the same remainder when divided by m, equivalently m divides (a − b). So 17 ≡ 5 (mod 12) because 17 − 5 = 12, and on a 12-hour clock 17:00 reads as 5. The set of remainders {0, 1, …, m−1} are the residue classes; every integer falls into exactly one. The power of the notation is that congruence behaves almost exactly like equality — you can add a constant, multiply by a constant, and substitute one side for the other without changing the relation. The CAT-useful instinct is to always replace a number by its smallest residue (or a convenient negative one) before doing anything: 99 ≡ −1 (mod 100), 8 ≡ 1 (mod 7), 6 ≡ −1 (mod 7). Choosing −1 turns a scary power into a sign question.
✅ Solved examples
✏️ Practice — try these, take hints as needed
📝 Topic test — 8 questions
Auto-graded with full solutions; saved to your dashboard. Use the calculator and formula sheet (top-right) any time.
Formula Reference Sheet
Congruence basics & operations
| Definition | a ≡ b (mod m) ⇔ m divides (a − b) |
|---|---|
| Addition | a ≡ b, c ≡ d ⇒ a + c ≡ b + d (mod m) |
| Multiplication | a ≡ b, c ≡ d ⇒ ac ≡ bd (mod m) |
| Exponentiation | a ≡ b (mod m) ⇒ a^k ≡ b^k (mod m) |
| Reduce the base first | a^k mod m = (a mod m)^k mod m |
Inverses, theorems & calendars
| Modular inverse | a·a⁻¹ ≡ 1 (mod m); exists ⇔ gcd(a, m) = 1 |
|---|---|
| Linear congruence ax ≡ b | solvable ⇔ gcd(a,m) divides b |
| Fermat’s little theorem | p prime, gcd(a,p)=1 ⇒ a^(p−1) ≡ 1 (mod p) |
| Euler’s theorem | gcd(a,m)=1 ⇒ a^φ(m) ≡ 1 (mod m) |
| Day shift | days mod 7 → 0=same weekday, 1=next day, … |