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 number theory is everywhere in contest problems. Here are the key concepts that actually made my solutions faster and cleaner.

Modular Arithmetic That Actually Works

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 going to have a bad time. Fast modular exponentiation saves the day:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def mod_pow(base: int, exponent: int, modulus: int) -> int:
    """
    Computes (base^exponent) % modulus efficiently.

    Args:
        base: Base number
        exponent: Power to raise to
        modulus: Modulus to apply
    
    Returns:
        int: The result of (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

Fermat’s Little Theorem Is Actually Useful

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 super handy for computing modular inverses. Instead of doing division in modular arithmetic (which is messy), you can multiply by the inverse:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def mod_inverse(a: int, m: int) -> int:
    """
    Computes modular multiplicative inverse using extended Euclidean algorithm.

    Args:
        a: Number to find inverse for
        m: Modulus
    
    Returns:
        int: The modular multiplicative inverse of a modulo m
    
    Raises:
        ValueError: If the modular inverse does not exist
    """
    def extended_gcd(a: int, b: int) -> tuple[int, int, int]:
        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
14
15
16
17
18
19
20
21
22
def chinese_remainder(remainders: list[int], moduli: list[int]) -> int:
    """
    Solves system of linear congruences using Chinese Remainder Theorem.

    Args:
        remainders: List of remainders
        moduli: List of moduli
    
    Returns:
        int: The smallest positive solution to the system of congruences
    """
    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|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 I Actually Use This Stuff

These concepts pop up more than you’d expect:

Chinese Remainder Theorem: Perfect for problems where you have multiple modular constraints that seem impossible to satisfy simultaneously.

Euler’s totient function: Great for counting problems involving coprime numbers or when you need to find patterns in modular exponentiation.

Fast modular arithmetic: Essential whenever you see big numbers and a modulus in the problem statement.

What I Learned

Number theory transforms what look like impossible problems into straightforward algorithms. The math might seem abstract at first, but once you see how it applies to actual contest problems, it becomes incredibly practical.

I’ve used these techniques in several contest solutions that you can check out in my competitive programming repository. The difference in both code clarity and performance is pretty significant.

If you want to discuss any of these concepts or have questions about specific applications, feel free to reach out.