Number Theory for Competitive Programming

, ,

After completing MA1301 at NTNU this semester, I’ve discovered how number theory fundamentally improves algorithmic problem-solving. Here’s an exploration of key concepts that I’ve found particularly useful in competitive programming.

Modular Arithmetic in Practice

The foundation of many algorithmic solutions lies in efficient modular arithmetic. When dealing with large numbers in contests, we often need to compute results modulo $10^9+7$ or similar primes. Here’s an implementation of fast modular exponentiation:

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

Applications of Fermat’s Little Theorem

Fermat’s Little Theorem states that for a prime $p$ and any integer $a$ not divisible by $p$:
$$a^{p-1}\equiv 1\pmod{p}$$
This theorem provides an elegant solution for computing modular multiplicative inverses:

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 Implementation

The Chinese Remainder Theorem (CRT) solves systems of congruences:

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

Implementation:

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

The Euler totient function $\phi\left(n\right)$ counts numbers coprime to $n$ up to $n$:

$$
\phi(n) = n\prod_{p|n}\left(1-\frac{1}{p}\right)
$$

This function is particularly useful in problems involving coprime pairs or modular exponentiation.

Practical Application

In recent contests and problems, these concepts have proven valuable:

  • Using CRT to solve problems with multiple modular constraints.
  • Applying Euler’s totient function for counting coprime pairs.
  • Implementing fast modular arithmetic for large number computations.

The elegance of number theory lies in its ability to transform complex problems into manageable algorithms. Understanding these mathematical foundations has significantly improved my approach to competitive programming.

You can find some of my solutions where I’ve applied these number theory concepts in my competitive programming repository.

Feel free to reach out if you’d like to discuss these concepts further.