Modular Operations
The reason congruences are a CAT weapon is that they survive addition, multiplication and powers. Concretely, a^k mod m equals (a mod m)^k mod m, so you reduce the base before raising it. To kill a large exponent, find a small power of the base that is ≡ 1 or ≡ −1, then ride the cycle. Example: for 2^500 mod 7, note 2^3 = 8 ≡ 1, so 2^500 = 2^(3×166+2) ≡ 1^166 × 2^2 = 4. The −1 trick is even faster: 6 ≡ −1 (mod 7) means 6^odd ≡ −1 ≡ 6 and 6^even ≡ 1. Two named shortcuts cut the work further. Fermat’s little theorem: for a prime p with gcd(a,p)=1, a^(p−1) ≡ 1 (mod p) — so 3^6 ≡ 1 (mod 7). Euler’s theorem generalises it to any modulus using φ(m). Reduce the exponent modulo (p−1) or φ(m), then finish off the small remaining power.
✅ 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, … |