# 📊 MODULAR ARITHMETIC: COMPLETE GUIDE 📊
## 🔍 BASIC CONCEPT
**Definition:** Modular arithmetic is a system where numbers "wrap around" after
reaching a fixed value (the modulus).
**Simple explanation:** Like a clock that goes from 1 to 12, then starts over again.
## ⭐ KEY PRINCIPLES
1. **Mod operation (%)**: Finds the remainder after division
- Example: 17 mod 5 = 2 (because 17 ÷ 5 = 3 with remainder 2)
2. **Congruence**: Two numbers are congruent modulo n if they have the same remainder
when divided by n
- Written as: a ≡ b (mod n)
- Example: 14 ≡ 2 (mod 4) because both leave remainder 2 when divided by 4
## 📝 DETAILED EXAMPLES
### Clock Arithmetic (mod 12):
- 10:00 + 6 hours = 4:00
- 10:00 + 24 hours = 10:00
- 3:00 + 20 hours = 11:00
### Computing with Various Moduli:
**Mod 5 System:**
- Values: 0, 1, 2, 3, 4
- 7 mod 5 = 2
- 12 mod 5 = 2
- 17 mod 5 = 2
- -3 mod 5 = 2 (because -3 = -1×5 + 2)
**Mod 12 Calculations:**
- 34 mod 12 = 10 (because 34 = 2×12 + 10)
- -17 mod 12 = 7 (because -17 = -2×12 + 7)
- -39 mod 12 = 9 (because -39 = -4×12 + 9)
- 58 mod 12 = 10 (because 58 = 4×12 + 10)
## 🧮 MODULAR ARITHMETIC OPERATIONS
### Addition:
- (a + b) mod n = [(a mod n) + (b mod n)] mod n
- Example: (14 + 23) mod 10 = [4 + 3] mod 10 = 7 mod 10 = 7
### Subtraction:
- (a - b) mod n = [(a mod n) - (b mod n)] mod n
- Example: (7 - 10) mod 8 = [7 - 2] mod 8 = 5 mod 8 = 5
### Multiplication:
- (a × b) mod n = [(a mod n) × (b mod n)] mod n
- Example: (15 × 18) mod 7 = [1 × 4] mod 7 = 4 mod 7 = 4
### Finding Inverses (when gcd(a,n) = 1):
- a × a^(-1) ≡ 1 (mod n)
- Example: 3 × 5 ≡ 15 ≡ 1 (mod 7), so 5 is the inverse of 3 mod 7
## 🔄 WORKING WITH SEQUENCES
### Sum of Arithmetic Sequence mod n:
- Sum of first k terms = [k(a₁ + aₖ)/2] mod n
- Example: Sum of 1,2,3,4,5,6 mod 7 = [6(1+6)/2] mod 7 = [21] mod 7 = 0
### Sum of Geometric Sequence mod n:
- Sum of first k terms = [a₁(1-r^k)/(1-r)] mod n
- Example: Sum of 2,4,8,16,32,64 mod 10 = [2(1-2^6)/(1-2)] mod 10 = [2(1-64)/(-1)] mod 10
= [2(-63)/(-1)] mod 10 = [126] mod 10 = 6
## 📐 MATHEMATICAL PROPERTIES
1. **Mathematical definition**: a ≡ b (mod n) if and only if n|(a-b)
- Example: 23 ≡ 8 (mod 5) because 5|(23-8)
2. **Equivalence relation properties**:
- Reflexive: a ≡ a (mod n)
- Symmetric: If a ≡ b (mod n), then b ≡ a (mod n)
- Transitive: If a ≡ b (mod n) and b ≡ c (mod n), then a ≡ c (mod n)
## 💻 APPLICATIONS IN COMPUTER SCIENCE
### Hash Tables:
- Using mod to convert large keys into array indices
- Example: Hash(1234567) = 1234567 mod 100 = 67
### Cryptography (RSA):
- Relies on modular exponentiation: a^b mod n
- Example: 5^117 mod 19 = 1
### Random Number Generation:
- Linear Congruential Generator: Xₙ₊₁ = (aXₙ + c) mod m
- Example: X₁ = (7×9 + 4) mod 15 = 67 mod 15 = 7
### Error Detection:
- Check digits using mod 10 or mod 11
- Example: ISBN verification using mod 11
## 🎨 VISUAL REPRESENTATION
Imagine numbers arranged in a circle:
- For mod 5: Only positions 0,1,2,3,4
- Moving clockwise = adding
- Moving counterclockwise = subtracting
- Complete rotations = multiples of the modulus
## ✏️PRACTICE PROBLEMS WITH SOLUTIONS
1. Calculate: 25 mod 12
- Solution: 25 = 2×12 + 1, so 25 mod 12 = 1
2. Solve: 7x ≡ 3 (mod 10)
- Find inverse of 7 mod 10: 7×3 ≡ 21 ≡ 1 (mod 10)
- Multiply both sides: 7x×3 ≡ 3×3 (mod 10)
- Therefore: x ≡ 9 (mod 10)
3. Find all solutions to: x² ≡ 1 (mod 8)
- Check each value: 0,1,2,3,4,5,6,7
- 0² mod 8 = 0, 1² mod 8 = 1, 2² mod 8 = 4, 3² mod 8 = 1, etc.
- Solutions: x ≡ 1,3,5,7 (mod 8)
4. Sum of sequence 3,7,11,15,19,23 mod 6
- Arithmetic sequence with a=3, d=4
- Sum = [6(3+23)/2] mod 6 = [6×13] mod 6 = 78 mod 6 = 0