Skip to content
Tutorials Center
My learning

Topics

Lesson 20 of 63 ยท Math for Contests

Modular Arithmetic

Master modular arithmetic for contests: mod 1e9+7, safe subtraction, pow with three arguments, modular inverses, division under a modulus and the traps of C++ remainders.

Contest problems love to say "print the answer modulo 1,000,000,007". The reason is practical: counting problems quickly produce numbers with thousands of digits, and the judges do not want to test big-number arithmetic. Instead they ask for the remainder after division by a fixed number, so every answer fits in a normal integer.

Python has arbitrary-size integers, so you could compute the full number and reduce at the end, but that is slow and wasteful. The right habit is to reduce after every operation, which keeps numbers small and fast. This lesson covers the rules of modular arithmetic, the one operation that needs care (division), and the differences you must know when reading solutions written in C++ or Java. For the background theory, see Number Theory and Fast Exponentiation.

The rules and the usual modulus

Two moduli appear again and again: 1_000_000_007 (written 10^9 + 7) and 998_244_353. Both are prime, which matters later for division. Call the modulus MOD. For addition, subtraction and multiplication, reducing early gives the same final answer:

  • (a + b) % MOD == ((a % MOD) + (b % MOD)) % MOD
  • (a - b) % MOD == ((a % MOD) - (b % MOD)) % MOD
  • (a * b) % MOD == ((a % MOD) * (b % MOD)) % MOD

These rules are why you can keep a running total with total = (total + x) % MOD instead of carrying a huge number. Division and comparison are the operations that do not survive reduction: you cannot tell whether one true answer is larger than another from their remainders.

flowchart LR
    A["Big exact value"] -->|"reduce mod M"| B["Small residue 0..M-1"]
    C["a, b residues"] -->|"+ - *"| D["Reduce after each step"]
    C -->|"division"| E["Multiply by modular inverse"]

Add, subtract and multiply are safe to reduce at every step; division needs an inverse.

Negative numbers: Python versus C++

In Python, a % m with a positive m always gives a result from 0 to m - 1, even when a is negative. In C++ and Java the remainder takes the sign of the left operand, so -3 % 5 is -3. Solutions in those languages write ((a % m) + m) % m to fix it. In Python you rarely need that, but you should recognize the pattern when you read editorials.

The same difference makes big multiplications dangerous elsewhere: in a 64-bit integer, a * b for two residues close to 10^9 + 7 reaches about 10^18, which still fits, but a product of three residues without reducing does not. Python never overflows, but the following TryIt simulates a 64-bit wraparound so you can see what the editorials are warning about.

Python Residues, negatives and a simulated overflow

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The take-away is that "reduce after every multiplication" is the rule in every language. In Python it is about speed and memory; in C++ it is also about correctness.

Powers and the three-argument pow

Python's built-in pow(base, exponent, modulus) computes base ** exponent % modulus using fast exponentiation, in about log(exponent) multiplications, and it never builds the huge intermediate number. That makes it the standard tool for questions like "what is 2^(10^18) mod 10^9 + 7?".

Since Python 3.8 the same function accepts a negative exponent with a modulus: pow(a, -1, m) returns the modular inverse of a, which is the number x with a * x % m == 1.

Division under a modulus

You cannot divide residues directly, because (a / b) % MOD is meaningless when the true quotient is not an integer. Instead you multiply by the inverse of b:

TEXT
a / b  (mod p)  =  a * inverse(b)  (mod p)

When MOD is prime and b is not a multiple of it, the inverse is pow(b, MOD - 2, MOD) by Fermat's little theorem, and pow(b, -1, MOD) gives the same value. If b and the modulus share a factor, no inverse exists and Python raises ValueError. That never happens for a prime modulus unless b is divisible by it.

Python Inverses and division

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The last two lines use a second consequence of Fermat's little theorem: for a prime p and a not divisible by p, a^(p-1) = 1 (mod p), so exponents can be reduced modulo p - 1. This matters when an exponent is itself a huge count computed modulo something.

Using it on real formulas

Typical contest formulas need division by small constants, such as 2 in n(n+1)/2 or r - 1 in a geometric series. When n is huge, you cannot reduce n(n+1) first and then divide by 2 using integer division, because the remainder has lost the information. Multiply by the inverse of 2 instead.

Python Formulas with division under a modulus

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Probabilities and averages are returned the same way: the statement says "print p * q^(-1) mod 998244353", and you compute exactly that with pow. We will return to this in Probability and Expected Value.

Common mistakes

  • Forgetting to reduce inside loops, which makes numbers huge and Python slow.
  • Dividing with // after reducing. Division needs pow(b, -1, MOD).
  • Using MOD - 2 for a composite modulus. Fermat's trick requires a prime modulus; pow(b, -1, m) works for any modulus when gcd(b, m) = 1.
  • Comparing residues. You cannot tell which exact answer is larger from the remainders.
  • Hard-coding the wrong constant. Check whether the problem uses 10^9 + 7 or 998244353.

For counting with these tools, continue with Counting and Combinatorics.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What does -3 % 5 evaluate to in Python?

    Python's remainder for a positive modulus is always between 0 and m - 1, so -3 % 5 is 2. C++ and Java would give -3.
  2. 2. How do you compute a / b modulo a prime p, assuming b is not a multiple of p?

    Division is replaced by multiplication with the modular inverse, available as pow(b, -1, p) or pow(b, p - 2, p) for prime p.
  3. 3. Why can pow(4, -1, 12) not succeed?

    An inverse exists only when the number and the modulus are coprime. Here they share the factor 4, so Python raises ValueError.
  4. 4. Which operation does NOT survive reduction modulo m at every step?

    Ring operations commute with reduction, but order information is lost, so you cannot compare residues to decide which true answer is bigger.
  5. 5. Why use pow(2, 1018, MOD) instead of 2 ** 1018 % MOD?

    The three-argument pow reduces during the computation in about log2(exponent) multiplications. The plain power would need an astronomically large number.

Summary

  • Answers "modulo 10^9 + 7" (or 998244353) keep numbers small; reduce after every operation.
  • Add, subtract and multiply commute with reduction; comparison and ordinary division do not.
  • Python's % with a positive modulus is never negative; C++ and Java need an extra fix.
  • pow(a, b, m) is fast exponentiation; pow(a, -1, m) is the modular inverse when gcd(a, m) = 1.
  • Divide by multiplying by the inverse; for a prime modulus pow(b, p - 2, p) is the same value.
  • For huge exponents, you may reduce them modulo p - 1 when the base is not a multiple of p.

Next: Counting and Combinatorics