{"title":"Modular Arithmetic","description":"","content":"Modular arithmetic is a fundamental tool in coding interviews, especially when dealing with large numbers, constraints, and repetitive patterns. It allows you to work within a fixed range by wrapping values around a modulus, which helps prevent overflow and keeps computations efficient.\n\nYou will encounter it in problems involving remainders, cyclic patterns, hashing, and combinatorics. The rest of this chapter covers the core arithmetic properties, the modulus `10^9 + 7`, fast exponentiation, and the modular inverse.\n\n---\n\n# What Is Modular Arithmetic?\n\nThe modulo operation gives you the remainder when one integer is divided by another. When we write `a % m` (or `a mod m`), we are asking: \"What is left over after dividing a by m?\"\n\nFor example:\n\n- 17 % 5 = 2 (because 17 = 3 * 5 + 2)\n- 10 % 3 = 1 (because 10 = 3 * 3 + 1)\n- 15 % 5 = 0 (because 15 = 3 * 5 + 0)\n\nOne way to picture this is as a clock face. If your modulus is 7, the positions 0 through 6 form a cycle, and counting forward past 6 wraps back to 0. So `10 mod 7 = 3`: starting at 0 and counting 10 steps on a 7-position clock means going around the full cycle once (7 steps) and landing 3 steps in.\n\n---\n\n# Key Properties of Modular Arithmetic\n\nThe power of modular arithmetic lies in its properties. These properties let you take the mod at every intermediate step of a computation, keeping numbers small, while still getting the correct final result.\n\n### Addition Property\n\n\n```shell\n(a + b) % m = ((a % m) + (b % m)) % m\n```\n\n\n**Example:** (15 + 23) % 7 = 38 % 7 = 3. Alternatively: (15 % 7 + 23 % 7) % 7 = (1 + 2) % 7 = 3. Same answer.\n\n### Multiplication Property\n\n\n```shell\n(a * b) % m = ((a % m) * (b % m)) % m\n```\n\n\n**Example:** (15 · 23) % 7 = 345 % 7 = 2. Alternatively: ((15 % 7) · (23 % 7)) % 7 = (1 · 2) % 7 = 2. Same answer.\n\n### Subtraction Property (Handling Negatives)\n\n\n```shell\n(a - b) % m = ((a % m) - (b % m) + m) % m\n```\n\n\nThe extra `+ m` is critical. In many programming languages (Java, C++, C#, JavaScript), the `%` operator can return negative values when the left operand is negative. For example, `-3 % 7` returns `-3` in Java, not `4`. Adding `m` before taking mod again ensures the result is always non-negative.\n\n**Example:** Compute (5 - 8) % 7. The mathematically correct remainder is 4, since `-3 = -1 · 7 + 4`. But in Java and C++, the expression `-3 % 7` evaluates to `-3`. The safe formula gives `((5 - 8) % 7 + 7) % 7 = (-3 + 7) % 7 = 4`.\n\n### Division Property (No Direct Division!)\n\nHere is the one operation that does NOT work the way you might expect:\n\n\n```shell\n(a / b) % m ≠ ((a % m) / (b % m)) % m ← WRONG\n```\n\n\nYou cannot simply divide and take mod. Instead, you need the **modular multiplicative inverse**, which we cover shortly. Division in modular arithmetic is performed by multiplying by the inverse.\n\n---\n\n# Why 10^9 + 7?\n\nYou will see the number 1000000007 (10^9 + 7) in countless problems. This is not arbitrary. It was chosen for very specific reasons:\n\n1. **It is prime.** This is essential because a prime modulus guarantees that every non-zero number has a modular inverse (thanks to Fermat's Little Theorem). Without a prime modulus, modular division would not always be possible.\n2. **It fits in a 32-bit integer.** The value 10^9 + 7 is approximately 1.07 × 10^9, well within the range of a 32-bit signed integer (max ≈ 2.1 × 10^9).\n3. **The product of two mod values fits in a 64-bit integer.** When you multiply two numbers each less than 10^9 + 7, the result is at most ~1.15 × 10^18, which fits in a 64-bit long (max ≈ 9.2 × 10^18). You can multiply two modded values and take mod again without overflow, as long as you use `long` for the intermediate.\n\n---\n\n# Modular Exponentiation (Binary Exponentiation)\n\nComputing `a^n mod m` is one of the most fundamental operations. The naive approach of multiplying `a` by itself `n` times is O(n), which is far too slow when n can be 10^9 or larger.\n\nBinary exponentiation (also called fast power or exponentiation by squaring) computes `a^n mod m` in O(log n) time. The key insight is based on the following recurrence:\n\n\n```shell\na^n = (a^(n/2))^2 if n is even\na^n = a * (a^(n/2))^2 if n is odd\na^0 = 1 base case\n```\n\n\nInstead of n multiplications, we only need log(n) multiplications because we halve the exponent at each step.\n\nThe iterative version processes the binary representation of the exponent from least significant bit to most significant bit. If the current bit is 1, multiply `result` by the current `base`. Either way, square the `base` and shift the exponent right. Here is the trace for `pow(2, 10, mod)`, where `10 = 1010` in binary:\n\n\n| Iteration | exp at start | bit (LSB) | result after step | base after squaring |\n|---|---|---|---|---|\n| start | 10 (`1010`) | - | 1 | 2 |\n| 1 | 10 | 0 | 1 (no change) | 4 |\n| 2 | 5 | 1 | 1 · 4 = 4 | 16 |\n| 3 | 2 | 0 | 4 (no change) | 256 |\n| 4 | 1 | 1 | 4 · 256 = 1024 | 65536 |\n| end | 0 | - | **1024** | - |\n\n\nFour iterations replace what would be ten multiplications in the naive approach. For an exponent like 10^18, this drops 10^18 operations to about 60.\n\n---\n\n# Modular Multiplicative Inverse\n\nThe modular inverse of `a` modulo `m` is a number `x` such that:\n\n\n```shell\n(a * x) % m = 1\n```\n\n\nWe write this as `a^(-1) mod m`. The inverse exists if and only if `gcd(a, m) = 1`. The reason follows from Bezout's identity: when `gcd(a, m) = 1`, there exist integers `x, y` with `a · x + m · y = 1`. Reduce both sides modulo `m`: the `m · y` term vanishes and we get `a · x ≡ 1 (mod m)`, so `x mod m` is the inverse. Conversely, if `gcd(a, m) = d > 1`, then every multiple of `a` is also a multiple of `d`, so `a · x` can never equal 1 modulo `m`. For composite `m`, the Extended Euclidean algorithm is the standard way to get the inverse.\n\nSince 10^9 + 7 is prime, every number from 1 to 10^9 + 6 is coprime to it and has an inverse.\n\n**Why do we need this?** Whenever you need to compute `(a / b) % m`, you instead compute `(a * b^(-1)) % m`, where `b^(-1)` is the modular inverse of `b`.\n\n### Fermat's Little Theorem\n\nWhen `m` is prime, Fermat's Little Theorem states:\n\n`a^(m-1) ≡ 1 (mod m)` for any `a` not divisible by `m`\n\nMultiply both sides by `a^(-1)`:\n\n`a^(m-2) ≡ a^(-1) (mod m)`\n\nSo the modular inverse is just `a^(m-2) mod m`, computable in `O(log m)` with the binary exponentiation function above. No new algorithm needed.\n\n\n```mermaid\nflowchart LR\n A[\"Need: (a / b) % m\"]\n B[\"Step 1:
Compute b^(m-2) % m
using fast power\"]\n C[\"Step 2:
Compute (a * b^(m-2)) % m\"]\n D[\"Result:
(a / b) % m\"]\n\n A --> B\n B --> C\n C --> D\n\n style A fill:#ff8787,stroke:#000,color:#000\n style B fill:#ffa94d,stroke:#000,color:#000\n style C fill:#38d9a9,stroke:#000,color:#000\n style D fill:#69db7c,stroke:#000,color:#000\n```\n\n\n**Example:** To compute `(6 / 3) % 7`, we need the inverse of 3 mod 7.\n\n- Inverse of 3 = 3^(7-2) % 7 = 3^5 % 7 = 243 % 7 = 5\n- Verify: (3 * 5) % 7 = 15 % 7 = 1. Correct.\n- So (6 / 3) % 7 = (6 * 5) % 7 = 30 % 7 = 2. And indeed, 6 / 3 = 2.\n\n---\n\n# Implementation\n\nBelow are complete implementations of modular exponentiation and modular inverse:\n\n\n```java\npublic class ModularArithmetic {\n static final long MOD = 1_000_000_007;\n\n // Computes (base^exp) % mod using binary exponentiation\n static long power(long base, long exp, long mod) {\n long result = 1;\n base %= mod;\n\n while (exp > 0) {\n if ((exp & 1) == 1) { // If current bit is 1\n result = (result * base) % mod;\n }\n exp >>= 1; // Shift right (divide by 2)\n base = (base * base) % mod;\n }\n\n return result;\n }\n\n // Computes modular inverse of a under mod (mod must be prime)\n static long modInverse(long a, long mod) {\n return power(a, mod - 2, mod);\n }\n\n // Safe modular subtraction\n static long modSubtract(long a, long b, long mod) {\n return ((a % mod) - (b % mod) + mod) % mod;\n }\n\n public static void main(String[] args) {\n System.out.println(power(2, 10, MOD)); // 1024\n System.out.println(modInverse(3, MOD)); // 333333336\n // Verify: (3 * 333333336) % MOD = 1\n System.out.println((3L * modInverse(3, MOD)) % MOD); // 1\n }\n}\n```\n\n```python\nMOD = 10**9 + 7\n\ndef power(base, exp, mod):\n \"\"\"Computes (base^exp) % mod using binary exponentiation.\"\"\"\n result = 1\n base %= mod\n\n while exp > 0:\n if exp & 1: # If current bit is 1\n result = (result * base) % mod\n exp >>= 1\n base = (base * base) % mod\n\n return result\n\ndef mod_inverse(a, mod):\n \"\"\"Computes modular inverse of a under mod (mod must be prime).\"\"\"\n return power(a, mod - 2, mod)\n\ndef mod_subtract(a, b, mod):\n \"\"\"Safe modular subtraction that avoids negative results.\"\"\"\n return ((a % mod) - (b % mod) + mod) % mod\n\n# Python also has built-in: pow(base, exp, mod) which does the same thing\nprint(power(2, 10, MOD)) # 1024\nprint(pow(2, 10, MOD)) # 1024 (built-in, equally fast)\nprint(mod_inverse(3, MOD)) # 333333336\n```\n\n```cpp\n#include \nusing namespace std;\n\nconst long long MOD = 1e9 + 7;\n\n// Computes (base^exp) % mod using binary exponentiation\nlong long power(long long base, long long exp, long long mod) {\n long long result = 1;\n base %= mod;\n\n while (exp > 0) {\n if (exp & 1) { // If current bit is 1\n result = (result * base) % mod;\n }\n exp >>= 1;\n base = (base * base) % mod;\n }\n\n return result;\n}\n\n// Computes modular inverse of a under mod (mod must be prime)\nlong long modInverse(long long a, long long mod) {\n return power(a, mod - 2, mod);\n}\n\n// Safe modular subtraction\nlong long modSubtract(long long a, long long b, long long mod) {\n return ((a % mod) - (b % mod) + mod) % mod;\n}\n\nint main() {\n cout << power(2, 10, MOD) << endl; // 1024\n cout << modInverse(3, MOD) << endl; // 333333336\n cout << (3LL * modInverse(3, MOD)) % MOD << endl; // 1\n return 0;\n}\n```\n\n```go\npackage main\n\nimport \"fmt\"\n\nconst MOD int64 = 1_000_000_007\n\n// Computes (base^exp) % mod using binary exponentiation\nfunc power(base int64, exp int64, mod int64) int64 {\n\tresult := int64(1)\n\tbase %= mod\n\n\tfor exp > 0 {\n\t\tif exp&1 == 1 { // If current bit is 1\n\t\t\tresult = (result * base) % mod\n\t\t}\n\t\texp >>= 1 // Shift right (divide by 2)\n\t\tbase = (base * base) % mod\n\t}\n\n\treturn result\n}\n\n// Computes modular inverse of a under mod (mod must be prime)\nfunc modInverse(a int64, mod int64) int64 {\n\treturn power(a, mod-2, mod)\n}\n\n// Safe modular subtraction\nfunc modSubtract(a int64, b int64, mod int64) int64 {\n\treturn ((a % mod) - (b % mod) + mod) % mod\n}\n\nfunc main() {\n\tfmt.Println(power(2, 10, MOD)) // 1024\n\tfmt.Println(modInverse(3, MOD)) // 333333336\n\tfmt.Println((3 * modInverse(3, MOD)) % MOD) // 1\n}\n```\n\n```csharp\npublic class ModularArithmetic\n{\n const long MOD = 1_000_000_007;\n\n // Computes (base^exp) % mod using binary exponentiation\n static long Power(long baseVal, long exp, long mod)\n {\n long result = 1;\n baseVal %= mod;\n\n while (exp > 0)\n {\n if ((exp & 1) == 1) // If current bit is 1\n {\n result = (result * baseVal) % mod;\n }\n exp >>= 1;\n baseVal = (baseVal * baseVal) % mod;\n }\n\n return result;\n }\n\n // Computes modular inverse of a under mod (mod must be prime)\n static long ModInverse(long a, long mod)\n {\n return Power(a, mod - 2, mod);\n }\n\n // Safe modular subtraction\n static long ModSubtract(long a, long b, long mod)\n {\n return ((a % mod) - (b % mod) + mod) % mod;\n }\n\n static void Main()\n {\n Console.WriteLine(Power(2, 10, MOD)); // 1024\n Console.WriteLine(ModInverse(3, MOD)); // 333333336\n Console.WriteLine((3L * ModInverse(3, MOD)) % MOD); // 1\n }\n}\n```\n\n```rust\nconst MOD: i64 = 1_000_000_007;\n\n// Computes (base^exp) % mod using binary exponentiation\nfn power(mut base: i64, mut exp: i64, m: i64) -> i64 {\n let mut result: i64 = 1;\n base %= m;\n\n while exp > 0 {\n if exp & 1 == 1 { // If current bit is 1\n result = (result * base) % m;\n }\n exp >>= 1; // Shift right (divide by 2)\n base = (base * base) % m;\n }\n\n result\n}\n\n// Computes modular inverse of a under m (m must be prime)\nfn mod_inverse(a: i64, m: i64) -> i64 {\n power(a, m - 2, m)\n}\n\n// Safe modular subtraction\nfn mod_subtract(a: i64, b: i64, m: i64) -> i64 {\n ((a % m) - (b % m) + m) % m\n}\n\nfn main() {\n println!(\"{}\", power(2, 10, MOD)); // 1024\n println!(\"{}\", mod_inverse(3, MOD)); // 333333336\n // Verify: (3 * 333333336) % MOD = 1\n println!(\"{}\", (3_i64 * mod_inverse(3, MOD)) % MOD); // 1\n}\n```\n\n```javascript\nconst MOD = 1000000007n; // Use BigInt for large mod operations\n\n// Computes (base^exp) % mod using binary exponentiation\nfunction power(base, exp, mod) {\n let result = 1n;\n base = base % mod;\n\n while (exp > 0n) {\n if (exp & 1n) { // If current bit is 1\n result = (result * base) % mod;\n }\n exp >>= 1n;\n base = (base * base) % mod;\n }\n\n return result;\n}\n\n// Computes modular inverse of a under mod (mod must be prime)\nfunction modInverse(a, mod) {\n return power(a, mod - 2n, mod);\n}\n\n// Safe modular subtraction\nfunction modSubtract(a, b, mod) {\n return ((a % mod) - (b % mod) + mod) % mod;\n}\n\nconsole.log(power(2n, 10n, MOD)); // 1024n\nconsole.log(modInverse(3n, MOD)); // 333333336n\nconsole.log((3n * modInverse(3n, MOD)) % MOD); // 1n\n```\n\n```typescript\nconst MOD: bigint = 1000000007n;\n\n// Computes (base^exp) % mod using binary exponentiation\nfunction power(base: bigint, exp: bigint, mod: bigint): bigint {\n let result: bigint = 1n;\n base = base % mod;\n\n while (exp > 0n) {\n if (exp & 1n) { // If current bit is 1\n result = (result * base) % mod;\n }\n exp >>= 1n;\n base = (base * base) % mod;\n }\n\n return result;\n}\n\n// Computes modular inverse of a under mod (mod must be prime)\nfunction modInverse(a: bigint, mod: bigint): bigint {\n return power(a, mod - 2n, mod);\n}\n\n// Safe modular subtraction\nfunction modSubtract(a: bigint, b: bigint, mod: bigint): bigint {\n return ((a % mod) - (b % mod) + mod) % mod;\n}\n\nconsole.log(power(2n, 10n, MOD)); // 1024n\nconsole.log(modInverse(3n, MOD)); // 333333336n\nconsole.log((3n * modInverse(3n, MOD)) % MOD); // 1n\n```\n\n\n---\n\n# Complexity Analysis\n\n\n| Operation | Time Complexity | Space Complexity |\n| --- | --- | --- |\n| Modular exponentiation (iterative) | O(log n) | O(1) |\n| Modular exponentiation (recursive) | O(log n) | O(log n) for call stack |\n| Modular inverse (via Fermat) | O(log m) | O(1) |\n| Single mod operation | O(1) | O(1) |\n\n\nThe iterative version is preferred in interviews and competitive programming because it avoids stack overflow for very large exponents and uses constant space.\n\nFor modular inverse, since we compute `a^(m-2) mod m` and m = 10^9 + 7, the time complexity is O(log(10^9 + 7)) which is roughly O(30), effectively constant.","pageType":"dsa"}

Modular Arithmetic

Get Premium