Number Theory for Competitive Programming

Some of the material from MA1301 at NTNU turned out to be useful in programming contests. I hadn’t expected that when I started the course, but modular arithmetic kept appearing in problems about counting, large exponents, and repeating events. These are the techniques I’ve found useful enough to keep nearby.

Fast modular exponentiation

Contest problems often ask for a result modulo a number such as \(10^9+7\). Computing \(2^{1000000}\) in full would do unnecessary work when we only need its remainder. Repeated squaring lets us compute \(a^n \bmod m\) in \(O(\log n)\) multiplications while reducing modulo \(m\) at each step:

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

Each iteration squares the base and reads one bit of the exponent. When that bit is set, we multiply the current base 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}\]

It follows that \(a^{p-2}\) is the modular inverse of \(a\) modulo \(p\). We can therefore divide by \(a\) in modular arithmetic by multiplying by that inverse, provided \(a\) is not divisible by \(p\).

For a composite modulus, the extended Euclidean algorithm can find an inverse when the number and the modulus are coprime:

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

A problem may give several remainders for the same unknown number:

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

If the moduli are pairwise coprime, the Chinese remainder theorem gives a unique solution modulo \(m_1 m_2 \cdots m_n\). The implementation constructs a term for each equation and adds them together:

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

This is useful when several periodic processes need to line up, with each process contributing a different modular constraint.

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)\]

Euler’s theorem uses this function to extend Fermat’s result to composite moduli: when \(a\) and \(n\) are coprime, \(a^{\phi(n)}\) is congruent to 1 modulo \(n\). The totient also appears in problems that count numbers coprime to a given integer.

When you actually use this

Recognizing the conditions for each theorem is as useful as remembering the implementation. Large exponents suggest repeated squaring, division modulo a number requires an inverse, and several periodic constraints may lead to the Chinese remainder theorem. Checking whether the modulus is prime or the inputs are coprime often determines which method applies.

I keep implementations in my competitive programming repo, along with the rest of the code I use for contests.