1. Modulo Arthmatics

---

1️⃣ Basic Modulo Rules

What is modulo?

Remainder after division. E.g., 10 % 3 = 1 and 14 % 5 = 4.

Core Identities

If we have two numbers $a$ and $b$ under modulo $m$, we perform operations as follows:

Operation	Mathematical Formula	Code Implementation	Why / Notes
➕ Addition	(a + b) % m	((a % m) + (b % m)) % m	Prevents overflow when adding huge numbers.
➖ Subtraction	(a - b) % m	((a % m) - (b % m) + m) % m	Add + m to avoid negative remainders in languages like C++/Java. (e.g. (3 - 7) % 5 $\to$ (-4 + 5) % 5 = 1).
✖️ Multiplication	(a * b) % m	((a % m) * (b % m)) % m	Prevents overflow when multiplying huge numbers.
➗ Division	(a / b) % m	(a * inverse(b)) % m	Cannot divide directly! Multiply by the modular multiplicative inverse: (a * b⁻¹) % m.

---

2️⃣ Negative Modulo Handling

Very common in LeetCode! In C++:
-3 % 5 = -3 (returns a negative remainder).

To normalize it to a positive remainder, use: mod = ((x % k) + k) % k;

Very useful in:

• Prefix sum
• Subarray sum
• Circular arrays

---

3️⃣ Same Remainder Bucketing

If a % k == b % k, then (a - b) % k == 0.
This means equal remainders belong to the same “bucket”.

Example

12 % 5 = 2 and 7 % 5 = 2
Therefore, 12 - 7 = 5, and 5 % 5 = 0.

Used in:

• Counting divisible subarrays
• Pairing problems

---

4️⃣ Complement Remainder Concept

Used for finding pairs that sum to a multiple of k.

To satisfy: (a + b) % k == 0
We need: b % k = (k - a % k) % k (Complement remainder)

Example

For k = 5:
If a % 5 = 2, we need a complement of 3 because 2 + 3 = 5.

Used in:

• Pair divisible by k
• Hashing pair problems

---

6️⃣ Cyclic Nature of Modulo

Modulo wraps around. E.g., for k = 5: 0, 1, 2, 3, 4, 0, 1, 2, 3, 4 ...

This acts like circular bucket indexing.

Circular Index Formula

idx = (i + shift) % n;

Used in:

• Circular arrays
• Rotations
• Matrix wrap-around

---

7️⃣ Common Bugs

Forgetting Negative Modulo

• ❌ Wrong: target = (curr - need) % p;
• ✅ Correct: target = (curr - need + p) % p;

Overflow Before Modulo

• ❌ Wrong: (a * b) % m
• ✅ Correct: ((a % m) * (b % m)) % m

---

🔗 Related Notes

• 2. Terms on leetcode

---