Number Theory for Competitive Programming

, ,

I took MA1301 at NTNU this semester and didn’t expect any of it to help with competitive programming. I was wrong. Number theory shows up constantly in contest problems, and once you start recognizing the patterns a whole class of problems becomes a lot easier.

Fast modular exponentiation

A lot of contest problems hand you huge numbers and ask for the result modulo \(10^9+7\). If you try to compute something like \(2^{1000000}\) the naive way, you’ll either overflow or time out. Fast modular exponentiation gets you there in \(O(\log n)\) time:

1
2
3
4
5
6
7
8
9
10
11
def mod_pow(base, exponent, modulus):
    if modulus == 1:
        return 0
    result = 1
    base = base % modulus
    while exponent > 0:
        if exponent & 1:
            result = (result * base) % modulus
        base = (base * base) % modulus
        exponent >>= 1
    return result

The trick is squaring the base on each iteration and using the bits of the exponent to decide when to fold it into the result.

Modular inverses with Fermat’s little theorem

Fermat’s little theorem says that for a prime \(p\) and any integer \(a\) not divisible by \(p\):

\[a^{p-1}\equiv 1\pmod{p}\]

Which means \(a^{p-2}\) is the modular inverse of \(a\) mod \(p\). Once you have that, dividing in modular arithmetic becomes multiplying by the inverse, which is much easier to reason about.

For non-prime moduli you fall back to the extended Euclidean algorithm:

1
2
3
4
5
6
7
8
9
10
11
12
13
def mod_inverse(a, m):
    def extended_gcd(a, b):
        if a == 0:
            return b, 0, 1
        gcd, x1, y1 = extended_gcd(b % a, a)
        x = y1 - (b // a) * x1
        y = x1
        return gcd, x, y

    gcd, x, _ = extended_gcd(a, m)
    if gcd != 1:
        raise ValueError("Modular inverse does not exist")
    return (x % m + m) % m

Chinese remainder theorem

Sometimes you get a system of modular equations that looks hopeless:

\[x \equiv a_1 \pmod{m_1}\] \[x \equiv a_2 \pmod{m_2}\] \[\vdots\] \[x \equiv a_n \pmod{m_n}\]

The Chinese remainder theorem says that if the moduli are pairwise coprime, there’s a unique solution modulo \(m_1 m_2 \cdots m_n\). The construction is careful bookkeeping more than anything else:

1
2
3
4
5
6
7
8
9
def chinese_remainder(remainders, moduli):
    total = 0
    product = 1
    for modulus in moduli:
        product *= modulus
    for remainder, modulus in zip(remainders, moduli):
        p = product // modulus
        total += remainder * p * mod_inverse(p, modulus)
    return total % product

I’ve used this for problems that combine multiple modular constraints, especially the ones where the constraints come from different periodic processes that happen to align somewhere in the future.

Euler’s totient function

The totient function \(\phi(n)\) counts how many integers in \([1, n]\) are coprime to \(n\). The product formula is:

\[\phi(n) = n \prod_{p \mid n} \left(1 - \frac{1}{p}\right)\]

This generalizes Fermat’s little theorem to non-prime moduli (Euler’s theorem) and shows up any time you need to count coprime pairs or simplify exponents in modular arithmetic.

When you actually use this

The thing that surprised me is how often these techniques show up in problems that look like they have nothing to do with number theory. A counting problem with periodic structure usually wants either CRT or the totient function. A problem with exponents in the millions usually wants fast modular exponentiation. A problem about cancellation in modular arithmetic usually wants modular inverses.

I keep a small toolkit of these in my competitive programming repo so I can drop them in when something looks familiar.