CONCEPT · Master
Modular arithmetic
also modexp · modpow · Fermat · modular inverse
Reduce after every multiply. Binary exponentiation is O(log e). Inverse of a mod a prime p is a^{p-2}. JS Number cannot hold (1e9+7)².
Intuition
You only ever need the remainder. Squaring halves the exponent; that is the speedup.
When to reach for it
- a^e mod m
- Modular inverse when m is prime
- Counting answers modulo 1e9+7
Usual pits
- Fermat on a composite modulus
- Negative a not reduced into [0,m)
- 0^0 conventions
- Exponent of a^{b^c} must reduce mod φ(m), not m
- JS IEEE overflow on 1e9*1e9 — use BigInt