aloalgoModular Arithmetic
Modular arithmetic is a system of arithmetic for integers where numbers wrap around after reaching a certain value (the modulus). It's essential for problems involving large numbers, as many require answers "modulo 10^9 + 7".Basic Properties
The key properties that make modular arithmetic useful:Modular Exponentiation
Computing a^n % m efficiently using binary exponentiation. This runs in O(log n) instead of O(n).Modular Inverse
The modular inverse of a (mod m) is a number x such that (a * x) % m = 1. It exists only when gcd(a, m) = 1 (a and m are coprime).Using Fermat's Little Theorem
When m is prime: a^(-1) ≡ a^(m-2) (mod m)Using Extended Euclidean Algorithm
Works for any modulus (not just primes), as long as gcd(a, m) = 1.Factorial and Combinations
Computing factorials and combinations with modular arithmetic requires precomputing inverses.Why 10^9 + 7?
This number (1000000007) is commonly used because:- It's a prime number (required for Fermat's Little Theorem)
- It fits in a 32-bit signed integer
- Product of two numbers < 10^9+7 fits in a 64-bit integer
Common Patterns
Sum of Range with Mod
Matrix Exponentiation
Used for computing nth Fibonacci or similar recurrences in O(log n).Complexity Summary
| Operation | Time |
|---|---|
| Basic Operations (+, -, *) | O(1) |
| Modular Exponentiation | O(log n) |
| Modular Inverse | O(log m) |
| Precompute n! and inverses | O(n) |
| C(n, r) with precomputation | O(1) |
Practice Problems
- Unique Paths - Can be solved with combinatorics: C(m+n-2, n-1)
Was this helpful?
Company
Practice
© 2026 aloalgo. All rights reserved.