Do numbers a aur b congruent modulo n hain (a ≡ b mod n) agar dono ko n se divide karne par same remainder mile — yaani n, (a−b) ko exactly divide kare.
a ≡ b (mod n) iff n | (a − b) [n divides a−b]
Examples:
17 ≡ 5 (mod 12) because 12 | (17−5) = 12 ✓
25 ≡ 4 (mod 7) because 7 | (25−4) = 21 ✓
100 ≡ 2 (mod 7) because 7 | (100−2) = 98 ✓
Properties of Congruences
Agar a ≡ b (mod n) aur c ≡ d (mod n), toh:
1. Reflexive: a ≡ a (mod n)
2. Symmetric: a ≡ b → b ≡ a (mod n)
3. Transitive: a ≡ b, b ≡ c → a ≡ c (mod n)
4. Addition: a+c ≡ b+d (mod n)
5. Subtraction: a−c ≡ b−d (mod n)
6. Multiplication: a×c ≡ b×d (mod n)
7. Power: aᵏ ≡ bᵏ (mod n)
Modular Arithmetic Table (mod 5)
+
0
1
2
3
4
0
0
1
2
3
4
1
1
2
3
4
0
2
2
3
4
0
1
3
3
4
0
1
2
4
4
0
1
2
3
Example: Day of the Week (Famous Application!)
Aaj Monday (day = 1). 100 din baad kaun sa din hoga? (Week = 7 days = mod 7)
1
100 mod 7 = ? → 100 = 14×7 + 2 → remainder = 2
2
1 + 2 = 3 → day 3 = Wednesday!
Day encoding: Mon=1, Tue=2, Wed=3, Thu=4, Fri=5, Sat=6, Sun=0
🔢 3. Applications of Modular Arithmetic
Divisibility Tests (Modulo se derive hote hain!)
Divisibility by 2: last digit ≡ 0 (mod 2)
Divisibility by 3: digit sum ≡ 0 (mod 3)
Divisibility by 4: last 2 digits ≡ 0 (mod 4)
Divisibility by 5: last digit ≡ 0 or 5 (mod 5)
Divisibility by 9: digit sum ≡ 0 (mod 9)
Divisibility by 11: alternating digit sum ≡ 0 (mod 11)
Example: Check Divisibility
Is 123456 divisible by 11?
Alternating sum = 1−2+3−4+5−6 = −3. −3 mod 11 = 8 ≠ 0 → Not divisible by 11
Is 13728 divisible by 9? Digit sum = 1+3+7+2+8 = 21. 21 mod 9 = 3 ≠ 0 → No
Fermat's Little Theorem (Board Exam Important!)
Agar p prime number hai aur a, p ka multiple nahi hai:
aᵖ⁻¹ ≡ 1 (mod p)
Application: Large powers mod prime nikaalte hain.
Example: 2¹⁰⁰ mod 7 = ?
p=7, so 2⁶ ≡ 1 (mod 7) [Fermat: 2⁷⁻¹ = 2⁶]
100 = 6×16 + 4
2¹⁰⁰ = (2⁶)¹⁶ × 2⁴ ≡ 1¹⁶ × 16 ≡ 16 ≡ 2 (mod 7)
Answer: 2¹⁰⁰ mod 7 = 2
Linear Congruences
ax ≡ b (mod n) solve karna — x ka value nikalna.
Condition: Solution exists iff gcd(a,n) divides b.
Example: 3x ≡ 4 (mod 7)
Inverse of 3 (mod 7): 3×5=15≡1 (mod 7) → 3⁻¹ = 5
x ≡ 5×4 = 20 ≡ 6 (mod 7)
Solution: x = 6, 13, 20, ... (x ≡ 6 mod 7)
💡 Board exam mein modulo aur congruence ke basic problems aate hain — remainders, day-of-week, last digit of powers. Practice karo!