Modular Arithmetic and pow(a, b, m)
20 min · Intermediate
Need help? Ask a tutor on WhatsApp (opens in a new tab)Many problems say "print the answer modulo 1,000,000,007". The true answer is too large, so only its remainder is asked for. Python has no overflow, but huge numbers are slow, so you keep them small by taking the remainder as you go. Python also has a built-in tool for fast powers.
The remainder, and % for negatives
Modular arithmetic is arithmetic where numbers are replaced by their remainder after division by a fixed number m, the modulus. Results always lie from 0 to m - 1.
The remainder of a divided by m is a % m. In Python it is never negative when m is positive, and it always matches floor division, so a == (a // m) * m + a % m holds for every integer.
print(17 % 5)print(-17 % 5)print(-17 // 5)Example 1 · Days of the week wrap around
day = 5print((day + 100) % 7)print((day - 10) % 7)0 2
What this code does
- Counting days from a Monday as 0, adding 100 days from day 5 lands on day 0.
- Going back 10 days gives a negative number, and Python's % still returns a day from 0 to 6, which is 2.
It prints 2, 3 and -4, because -17 is -4 * 5 + 3. Some other languages give -2 for the second line, so check this before copying a C or Java answer.
Add, subtract and multiply under a modulus
You may take the remainder at any step and the final remainder stays the same, for +, - and *. So keep every value below m while you loop, and the numbers never grow large.
MOD = 1_000_000_007a, b = 987_654_321, 876_543_210print((a * b) % MOD)print(((a % MOD) * (b % MOD)) % MOD)Example 2 · A factorial under a modulus
import math
MOD = 1_000_000_007result = 1for i in range(1, 21): result = result * i % MODprint(result)print(math.factorial(20) % MOD)146326063 146326063
What this code does
- The loop keeps
resultbelow the modulus at every step. - Both lines print the same number, so reducing early changes nothing except the size of the numbers.
Both lines print the same number. In a long loop, write result = result * x % MOD at each step so that result stays small. Division is different and needs an inverse, shown below.
pow(a, b, m): fast power with a modulus
Modular exponentiation is computing a to the power b, modulo m, by repeated squaring. Python does it in pow(a, b, m) in O(log b) steps.
a ** b with big b makes a huge number. The three-argument pow(a, b, m) squares and multiplies while reducing modulo m each time, so it needs only about log2(b) steps and never builds the big number.
print(pow(2, 10))print(pow(2, 10, 1000))print(pow(3, 10**18, 1_000_000_007))Example 3 · Fast power written by hand
def power(base, exp, mod): result = 1 base %= mod while exp: if exp & 1: result = result * base % mod base = base * base % mod exp >>= 1 return result
print(power(3, 200, 13), pow(3, 200, 13))9 9
What this code does
- Square the base each round and multiply it in whenever the current lowest bit of the exponent is 1.
- The loop runs once per bit of the exponent. Both calls give the same answer. Interviews like the hand-written form, real code uses
pow.
Example 4 · Last digits of a huge power
print(pow(2, 100, 10))print(pow(7, 2024, 100))6 1
What this code does
- A modulus of 10 keeps the last digit and 100 keeps the last two.
- The last digit of 2 to the 100 is 6. The last two digits of 7 to the 2024 are 01, which print as 1, because 7 to the 4 ends in 01.
The second line is 1024 % 1000, which is 24. The third line has an exponent of a million million million and still answers at once.
Modular inverse: dividing under a modulus
A modular inverse of a under modulus m is a number inv where a * inv % m is 1. It exists only when a and m are coprime, and it replaces division.
You cannot divide under a modulus with /. Instead multiply by the inverse: the number inv with a * inv leaving remainder 1. Since Python 3.8, pow(a, -1, m) finds it, as long as a and m share no factor.
MOD = 1_000_000_007inv = pow(2, -1, MOD)print(inv)print(inv * 2 % MOD)print(10 * pow(2, -1, MOD) % MOD)Example 5 · Combinations under a modulus
MOD = 1_000_000_007
def ncr(n, r): num = den = 1 for i in range(r): num = num * (n - i) % MOD den = den * (i + 1) % MOD return num * pow(den, -1, MOD) % MOD
print(ncr(10, 3), ncr(1000, 500))120 159835829
What this code does
- nCr is a product of r numbers divided by r factorial. The division is done with the modular inverse.
- ncr(10, 3) is 120. The second answer is a huge number reduced modulo 1,000,000,007.
The inverse of 2 is 500000004, because twice that is one more than the modulus. Dividing 10 by 2 under the modulus gives 5, as expected.
Next step
Check your understanding
10 quick questions