Number Theory for Competitive Programming

Interview-style DSA rarely asks you to compute $\binom{1000}{500} \bmod (10^9 + 7)$ or find every prime under ten million — but competitive programming asks for exactly that, constantly. This lesson is the number theory toolkit that shows up over and over in contests: it’s less about clever tricks and more about a handful of building blocks you’ll reuse in dozens of problems.

What you’ll learn

GCD, LCM, and Euclid’s algorithm — the foundation everything else builds on.
Modular arithmetic rules for add/subtract/multiply, and why division needs special handling.
Fast modular exponentiation — computing $a^b \bmod m$ in $O(\log b)$ instead of $O(b)$ .
Modular inverse via Fermat’s little theorem, so division under a modulus becomes multiplication.
The Sieve of Eratosthenes for finding every prime up to $n$ , plus a pointer to the linear sieve.
Prime factorization and combinatorics mod p with precomputed factorials — answering $\binom{n}{k} \bmod p$ in $O(1)$ per query.

GCD, LCM, and Euclid’s algorithm

The greatest common divisor of two numbers can be found without ever listing their factors: gcd(a, b) == gcd(b, a % b)gcd(a, b) == gcd(b, a % b), and the recursion bottoms out the moment the second argument hits 00.

gcd_lcm.py

import math
 
 
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
 
 
def lcm(a, b):
    return a * b // gcd(a, b)
 
 
print("gcd(48, 18):", gcd(48, 18))            # 6
print("lcm(4, 6):", lcm(4, 6))                # 12
print("math.gcd matches:", math.gcd(48, 18))  # stdlib version -- use this in practice
print("math.lcm matches:", math.lcm(4, 6))    # Python 3.9+

gcd_lcm.py

import math
 
 
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
 
 
def lcm(a, b):
    return a * b // gcd(a, b)
 
 
print("gcd(48, 18):", gcd(48, 18))            # 6
print("lcm(4, 6):", lcm(4, 6))                # 12
print("math.gcd matches:", math.gcd(48, 18))  # stdlib version -- use this in practice
print("math.lcm matches:", math.lcm(4, 6))    # Python 3.9+

diagram Euclid's algorithm: gcd(48, 18) shrinks to 0 in three steps mermaid

  graph LR
    N0["gcd(48, 18)"] --> N1["gcd(18, 12)"]
    N1 --> N2["gcd(12, 6)"]
    N2 --> N3["gcd(6, 0) = 6"]

Each step replaces (a, b)(a, b) with (b, a % b)(b, a % b), and a % ba % b is always smaller than bb — so the pair shrinks fast (logarithmically) no matter how large aa and bb start out.

Modular arithmetic rules

Contest answers are usually taken $\bmod\ p$ for a large prime like $10^9 + 7$ , both to keep numbers bounded and to give a clean, unique answer. Addition, subtraction, and multiplication all distribute cleanly over the modulus:

(a + b) \bmod m = \bigl((a \bmod m) + (b \bmod m)\bigr) \bmod m

(a - b) \bmod m = \bigl((a \bmod m) - (b \bmod m) + m\bigr) \bmod m

(a \cdot b) \bmod m = \bigl((a \bmod m) \cdot (b \bmod m)\bigr) \bmod m

The + m+ m in the subtraction rule matters in Python less than in most other languages (Python’s %% always returns a non-negative result for a positive modulus), but it’s worth keeping the habit — it’s what makes the rule portable to any language.

Division is the odd one out: $(a / b) \bmod m$ is not $\bigl((a \bmod m) / (b \bmod m)\bigr) \bmod m$ in general. Division under a modulus needs the modular inverse, covered below.

Fast modular exponentiation

Computing $a^b \bmod m$ by multiplying aa into an accumulator bb times is $O(b)$ — far too slow when bb is $10^9$ or more. Binary exponentiation cuts this to $O(\log b)$ by squaring the base and only folding it into the result on the bits of bb that are 11:

mod_pow.py

def power_mod(base, exp, mod):
    result = 1
    base %= mod
    while exp > 0:
        if exp & 1:                       # this bit of exp is 1 -> fold the current base in
            result = (result * base) % mod
        base = (base * base) % mod        # square the base for the next bit
        exp >>= 1                          # move to the next bit
    return result
 
 
print("3^13 mod 7:", power_mod(3, 13, 7))
print("built-in pow() does the same:", pow(3, 13, 7))

mod_pow.py

def power_mod(base, exp, mod):
    result = 1
    base %= mod
    while exp > 0:
        if exp & 1:                       # this bit of exp is 1 -> fold the current base in
            result = (result * base) % mod
        base = (base * base) % mod        # square the base for the next bit
        exp >>= 1                          # move to the next bit
    return result
 
 
print("3^13 mod 7:", power_mod(3, 13, 7))
print("built-in pow() does the same:", pow(3, 13, 7))

sketch Binary exponentiation: consuming exp one bit at a time p5.js

Each step squares the base; a lit bit (gold) folds the current base into the running result.

Modular inverse via Fermat’s little theorem

Division under a modulus works by multiplying by the modular inverse of the divisor instead. When the modulus $p$ is prime, Fermat’s little theorem gives a one-line formula:

a^{-1} \equiv a^{p-2} \pmod p

mod_inverse.py

MOD = 1_000_000_007
 
 
def mod_inverse(a, mod=MOD):
    return pow(a, mod - 2, mod)       # valid ONLY when mod is prime (Fermat's little theorem)
 
 
a = 123456
inv = mod_inverse(a)
print("inverse of", a, "mod", MOD, ":", inv)
print("check: a * inv mod p == 1 ->", (a * inv) % MOD == 1)

mod_inverse.py

MOD = 1_000_000_007
 
 
def mod_inverse(a, mod=MOD):
    return pow(a, mod - 2, mod)       # valid ONLY when mod is prime (Fermat's little theorem)
 
 
a = 123456
inv = mod_inverse(a)
print("inverse of", a, "mod", MOD, ":", inv)
print("check: a * inv mod p == 1 ->", (a * inv) % MOD == 1)

Sieve of Eratosthenes

Finding every prime up to some limit nn by trial-dividing each number individually is O(n sqrt(n))O(n sqrt(n)). The sieve flips the approach: start every number as “prime”, then cross off every multiple of each prime found, starting from its square (smaller multiples were already crossed off by a smaller prime).

sieve.py

def sieve_of_eratosthenes(limit):
    is_prime = [True] * (limit + 1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(limit ** 0.5) + 1):
        if is_prime[i]:
            for multiple in range(i * i, limit + 1, i):
                is_prime[multiple] = False
    return [i for i, prime in enumerate(is_prime) if prime]
 
 
primes = sieve_of_eratosthenes(50)
print("primes up to 50:", primes)
print("count:", len(primes))

sieve.py

def sieve_of_eratosthenes(limit):
    is_prime = [True] * (limit + 1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(limit ** 0.5) + 1):
        if is_prime[i]:
            for multiple in range(i * i, limit + 1, i):
                is_prime[multiple] = False
    return [i for i, prime in enumerate(is_prime) if prime]
 
 
primes = sieve_of_eratosthenes(50)
print("primes up to 50:", primes)
print("count:", len(primes))

sketch Sieve of Eratosthenes: crossing off multiples of each prime p5.js

Gold = the current prime i. Blue = still believed prime. Gray = crossed off (composite).

Prime factorization

Once you have primes (or even without a sieve, for a single number), trial division up to $\sqrt{n}$ finds every prime factor and its exponent:

prime_factorization.py

def prime_factorize(n):
    factors = {}
    d = 2
    while d * d <= n:
        while n % d == 0:
            factors[d] = factors.get(d, 0) + 1
            n //= d
        d += 1
    if n > 1:                 # whatever's left over is itself a prime factor
        factors[n] = factors.get(n, 0) + 1
    return factors
 
 
print(prime_factorize(360))   # {2: 3, 3: 2, 5: 1}  ->  2^3 * 3^2 * 5 = 360
print(prime_factorize(97))    # {97: 1}  --  97 is prime

prime_factorization.py

def prime_factorize(n):
    factors = {}
    d = 2
    while d * d <= n:
        while n % d == 0:
            factors[d] = factors.get(d, 0) + 1
            n //= d
        d += 1
    if n > 1:                 # whatever's left over is itself a prime factor
        factors[n] = factors.get(n, 0) + 1
    return factors
 
 
print(prime_factorize(360))   # {2: 3, 3: 2, 5: 1}  ->  2^3 * 3^2 * 5 = 360
print(prime_factorize(97))    # {97: 1}  --  97 is prime

Combinatorics mod p: nCr with precomputed factorials

\binom{n}{k} = \frac{n!}{k! \, (n-k)!}

Computing this directly under a modulus needs the modular inverses of k!k! and (n - k)!(n - k)! — and precomputing every factorial and inverse factorial up to the largest nn you’ll ever need turns each individual query into an $O(1)$ lookup, which matters when a problem asks for thousands of nCrnCr queries.

ncr_mod_p.py

MOD = 1_000_000_007
MAX_N = 200_000
 
fact = [1] * (MAX_N + 1)
for i in range(1, MAX_N + 1):
    fact[i] = fact[i - 1] * i % MOD
 
inv_fact = [1] * (MAX_N + 1)
inv_fact[MAX_N] = pow(fact[MAX_N], MOD - 2, MOD)   # one Fermat inverse, at the top
for i in range(MAX_N, 0, -1):
    inv_fact[i - 1] = inv_fact[i] * i % MOD         # (n-1)!^-1 = n!^-1 * n, walking down
 
 
def n_choose_k(n, k):
    if k < 0 or k > n:
        return 0
    return fact[n] * inv_fact[k] % MOD * inv_fact[n - k] % MOD
 
 
print("C(10, 3):", n_choose_k(10, 3))                       # 120
print("C(1000, 500) mod 1e9+7:", n_choose_k(1000, 500))

ncr_mod_p.py

MOD = 1_000_000_007
MAX_N = 200_000
 
fact = [1] * (MAX_N + 1)
for i in range(1, MAX_N + 1):
    fact[i] = fact[i - 1] * i % MOD
 
inv_fact = [1] * (MAX_N + 1)
inv_fact[MAX_N] = pow(fact[MAX_N], MOD - 2, MOD)   # one Fermat inverse, at the top
for i in range(MAX_N, 0, -1):
    inv_fact[i - 1] = inv_fact[i] * i % MOD         # (n-1)!^-1 = n!^-1 * n, walking down
 
 
def n_choose_k(n, k):
    if k < 0 or k > n:
        return 0
    return fact[n] * inv_fact[k] % MOD * inv_fact[n - k] % MOD
 
 
print("C(10, 3):", n_choose_k(10, 3))                       # 120
print("C(1000, 500) mod 1e9+7:", n_choose_k(1000, 500))

Only one expensive pow(..., MOD - 2, MOD)pow(..., MOD - 2, MOD) call is needed in the whole setup — every other inverse factorial is derived from the next one with a single multiplication, since inv_fact[i - 1] = inv_fact[i] * i % MODinv_fact[i - 1] = inv_fact[i] * i % MOD falls straight out of fact[i] = fact[i - 1] * ifact[i] = fact[i - 1] * i.

Complexity

Task	Naive	Optimized	Notes
GCD	—	$O(\log(\min(a, b)))$	Euclid’s algorithm
$a^b \bmod m$	$O(b)$	$O(\log b)$	Binary (fast) exponentiation
Modular inverse	—	$O(\log p)$	Fermat’s little theorem, requires prime modulus
Primes up to $n$	$O(n \sqrt{n})$ trial division	$O(n \log \log n)$	Sieve of Eratosthenes ( $O(n)$ with a linear sieve)
$\binom{n}{k} \bmod p$ , many queries	$O(k)$ per query	$O(n)$ precompute, $O(1)$ per query	Precomputed factorials + inverse factorials

Practice — real LeetCode problems

A sieve, a GCD in disguise, and a problem that is one theorem long once you recognise it.

LC 204 — Count Primes · Medium

Problem. Return the number of prime numbers strictly less than nn.

Constraints. 0 <= n <= 5 * 10**60 <= n <= 5 * 10**6.

Examples. n = 10n = 10 gives 44 (2, 3, 5, 7) · n = 0n = 0 gives 00 · n = 1n = 1 gives 00

Editorial · approach, complexity, follow-ups

Time $O(n \log \log n)$ — the sum of $n/p$ over primes $p$ below $n$ . Effectively linear, and the number to quote. Space $O(n)$ bits.

Both optimisations have one-line justifications, and both get asked about:

Start at $p^2$ . Any multiple $kp$ with $k < p$ has a prime factor smaller than $p$ , so it was already crossed out on an earlier pass.
Stop when $p^2 \ge n$ . A composite below $n$ must have a prime factor at most $\sqrt{n}$ , so every composite is already gone.
Strictly less than nn. n = 3n = 3 gives 1 (just the 2), and n = 2n = 2 gives 0. Off-by-one here is the most common wrong answer on the problem.
n = 0n = 0 and n = 1n = 1 must not index sieve[1]sieve[1], hence the early return. A bare [True] * n[True] * n with sieve[0] = sieve[1] = Falsesieve[0] = sieve[1] = False crashes on n = 0n = 0 and n = 1n = 1.
p * p < np * p < n, not p * p <= np * p <= n — with indices running to n - 1n - 1, a pp where p * p == np * p == n has no multiple inside the array anyway. Either bound is correct here; the strict one matches the index range exactly.
sum(sieve)sum(sieve) works because TrueTrue is 1. Cute, and fine to use.

In Python the inner loop is often written as a slice assignment, sieve[p*p::p] = [False] * len(sieve[p*p::p])sieve[p*p::p] = [False] * len(sieve[p*p::p]), which pushes the work into C and is several times faster. Worth showing after the explicit loop.

Follow-ups you should expect: “List the primes, not the count?” — the same sieve, then enumerate. “Primes up to $10^{12}$ ?” — a plain sieve needs too much memory; use a segmented sieve, and mention Miller-Rabin for testing a single large number. “Smallest prime factor of every number?” — store pp instead of FalseFalse during the sieve; that gives $O(\log n)$ factorisation per query afterwards. “Prime factorise one number?” — trial division to $\sqrt{n}$ is enough. “Count primes in a range [a, b][a, b]?” — segmented sieve, or two prefix counts.

LC 1071 — Greatest Common Divisor of Strings · Easy

Problem. A string tt divides ss if ss is tt repeated some number of times. Return the longest string that divides both str1str1 and str2str2, or """" if there is none.

Constraints. 1 <= len(str1), len(str2) <= 10001 <= len(str1), len(str2) <= 1000, uppercase English letters.

Examples. "ABCABC""ABCABC" and "ABC""ABC" gives "ABC""ABC" · "ABABAB""ABABAB" and "ABAB""ABAB" gives "AB""AB" · "LEET""LEET" and "CODE""CODE" gives """"

Editorial · approach, complexity, follow-ups

A number-theory identity wearing a string costume. Once you see that string concatenation behaves like addition of exponents over a common base, the whole problem is two lines.

Why commuting is the right test. If both strings are repetitions of a common base tt, then str1 + str2str1 + str2 and str2 + str1str2 + str1 are both tt repeated (len(str1) + len(str2)) / len(t)(len(str1) + len(str2)) / len(t) times, so they are equal. The converse is the non-obvious direction — it is a standard result that xy = yxxy = yx for strings forces both to be powers of a common word. You are not expected to prove it at a whiteboard, but you should state that you are using it rather than pretend it is obvious.

Why the length is the GCD. Any common divisor’s length divides both lengths, so it divides their GCD; and given that a common divisor exists, the prefix of that GCD length is one. So it is the longest.

Time $O(m + n)$ for the concatenation and comparison. Space $O(m + n)$ for the two temporary strings.

Return """", not NoneNone, when there is no common divisor.
"LEET""LEET" and "CODE""CODE" have GCD length 4, so a length check alone would wrongly return "LEET""LEET". The commuting test is what rejects it — skipping it is the classic wrong solution that passes the first two examples.
str1[:g]str1[:g] versus str2[:g]str2[:g] — once the strings commute, both prefixes are identical, so either works.
Equal strings return the whole string, since the GCD of nn and nn is nn.

Follow-ups you should expect: “Prove it, or at least test it without the theorem?” — take the candidate prefix of GCD length and verify it repeats to build both strings; still $O(m + n)$ and much easier to defend. “Repeated Substring Pattern (LC 459)?” — the same family: ss is a repetition if ss appears in (s + s)[1:-1](s + s)[1:-1]. “Shortest string both divide (the LCM)?” — exists exactly when a GCD does, with length lcm(m, n)lcm(m, n). “Why does math.gcdmath.gcd suffice?” — it is Euclid’s algorithm in C, $O(\log \min(m, n))$ .

LC 1250 — Check If It Is a Good Array · Hard

Problem. You may pick a subset of numsnums, multiply each chosen number by any integer, and add the results. The array is good if some choice sums to exactly 1. Return whether it is good.

Constraints. 1 <= len(nums) <= 10**51 <= len(nums) <= 10**5, 1 <= nums[i] <= 10**91 <= nums[i] <= 10**9.

Examples. [12,5,7,23][12,5,7,23] gives TrueTrue · [29,6,10][29,6,10] gives TrueTrue · [3,6][3,6] gives FalseFalse

Editorial · approach, complexity, follow-ups

Bezout’s identity. For integers $a$ and $b$ , the set $\{ax + by : x, y \in \mathbb{Z}\}$ is exactly the set of multiples of $\gcd(a, b)$ . Extended to $n$ numbers: the reachable sums are precisely the multiples of the GCD of all of them. So 1 is reachable exactly when that GCD is 1 — when the numbers are setwise coprime.

Note this is setwise coprime, not pairwise. [6,10,15][6,10,15] has no two elements coprime, yet the GCD of all three is 1, so it is good. Being able to draw that distinction is most of what the problem is testing.

Time $O(n \log \max)$ . Space $O(1)$ .

Seed with 0. gcd(0, x) == xgcd(0, x) == x, so 0 is the correct identity element for folding. Seeding with nums[0]nums[0] also works but needs a guard for an empty array.
The early exit is safe because gcd(1, x) == 1gcd(1, x) == 1 always — once the running GCD is 1 it stays 1. Not required for correctness, but a natural thing to point out.
[3,6][3,6] is FalseFalse. Every reachable sum is a multiple of 3, and 1 is not.
[1][1] is TrueTrue — pick the 1 and multiply by 1.
The multipliers may be negative, which is what makes [29,6,10][29,6,10] work: for example $29 \cdot 1 + 6 \cdot (-5) + 10 \cdot 0 = -1$ , then negate. If the multipliers were restricted to non-negative integers this would be the Frobenius coin problem, which is a genuinely different and much harder question.

Follow-ups you should expect: “Find the actual multipliers?” — the extended Euclidean algorithm, folded across the array. “Reach some other target tt?” — tt is reachable exactly when the GCD divides it. “Non-negative multipliers only?” — the Chicken McNugget / Frobenius problem; no simple closed form beyond two numbers. “Why is this rated Hard?” — purely for the recognition step; the code is four lines and that gap is the lesson.

LeetCode problem set

#	Problem	Difficulty	The twist
204	Count Primes	Medium	The Sieve of Eratosthenes above, applied directly to count primes below a limit
264	Ugly Number II	Medium	Not a sieve, but the same “multiples of small primes” thinking: merge three pointers tracking multiples of 2, 3, and 5
279	Perfect Squares	Medium	Usually solved with DP, but Lagrange’s four-square theorem (every positive integer is a sum of at most four perfect squares) gives a number-theory shortcut most solvers never see
1390	Four Divisors	Medium	Sum the divisors of every number that has exactly four of them; a direct application of prime factorization

Recap

GCD/LCM: Euclid’s algorithm shrinks (a, b)(a, b) to gcdgcd in $O(\log(\min(a, b)))$ ; use math.gcdmath.gcd and math.lcmmath.lcm in practice.
Modular arithmetic: add/subtract/multiply distribute cleanly over a modulus; division needs the modular inverse instead.
Fast exponentiation: $O(\log b)$ via squaring, or just call pow(a, b, m)pow(a, b, m).
Modular inverse: pow(a, p - 2, p)pow(a, p - 2, p) for prime pp, via Fermat’s little theorem.
Sieve of Eratosthenes: $O(n \log \log n)$ to find every prime up to nn; a linear sieve reaches true $O(n)$ when needed.
nCr mod p: precompute factorials and inverse factorials once, then answer every query in $O(1)$ .

That closes out the sparse table and number theory building blocks — between static-array RMQ and this modular-arithmetic toolkit, you can now recognize and solve a large share of the “math-flavored” problems that show up throughout competitive programming.

Next: String Algorithms: KMP, Z, and Rabin-Karp — linear-time pattern matching, the other family of classic CP building blocks that shows up just as often as the number theory above.

If this helped you, consider buying me a coffee ☕

Buy me a coffee

Number Theory for Competitive Programming

What you’ll learn

GCD, LCM, and Euclid’s algorithm

Modular arithmetic rules

Fast modular exponentiation

Modular inverse via Fermat’s little theorem

Sieve of Eratosthenes

Prime factorization

Combinatorics mod p: nCr with precomputed factorials

Complexity

Practice — real LeetCode problems

LC 204 — Count Primes · Medium

LC 1071 — Greatest Common Divisor of Strings · Easy

LC 1250 — Check If It Is a Good Array · Hard

LeetCode problem set

Recap

Was this page helpful?