Number Theory for Competitive Programming

, ,

I took MA1301 at NTNU this semester and honestly didn’t expect it to help much with competitive programming. Turns out I was completely wrong – number theory shows up everywhere in contest problems.

Fast Exponentiation

Contest problems love throwing around huge numbers and asking for results modulo \(10^9+7\). If you try to compute something like \(2^{1000000}\) the normal way, you’re gonna have a bad time. This is where fast modular exponentiation comes in:

1
2
3
4
5
6
7
8
9
10
11
12
13
def mod_pow(base, exponent, modulus):
    # Computes (base^exponent) % modulus efficiently
    if modulus == 1:
        return 0
    
    result = 1
    base = base % modulus
    while exponent > 0:
        if exponent & 1:  # if exponent is odd
            result = (result * base) % modulus
        base = (base * base) % modulus
        exponent >>= 1  # divide exponent by 2
    return result

Modular Inverses with Fermat

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

This is really handy for computing modular inverses. Instead of doing division in modular arithmetic (which is messy), you just multiply by the inverse:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def mod_inverse(a, m):
    # Extended Euclidean algorithm to find modular inverse
    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 problems with multiple modular constraints that look impossible. The Chinese Remainder Theorem handles systems like:

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

Here’s how to solve them:

1
2
3
4
5
6
7
8
9
10
11
12
13
def chinese_remainder(remainders, moduli):
    # Solves system of congruences using Chinese Remainder Theorem
    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

Euler’s Totient Function

Euler’s totient function \(\phi(n)\) counts how many numbers less than or equal to \(n\) are coprime to \(n\). The formula is:

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

This shows up in problems about counting coprime pairs or when you need to apply Euler’s theorem for modular exponentiation.

When This Stuff Actually Comes Up

So when do you actually use these? More often than you’d think. Chinese Remainder Theorem is perfect for problems where you have multiple modular constraints that seem impossible to satisfy at once. Euler’s totient function shows up in counting problems with coprime numbers. And fast modular arithmetic? Basically any time you see big numbers with a modulus.

The cool thing is how these transform what looks like impossible problems into something you can actually code up. The math might seem abstract when you’re learning it, but once you start seeing it in contest problems, it clicks.

I’ve got a bunch of solutions using these techniques in my competitive programming repository if you want to see them in action.