18.25 Number Theory Toolkit

After working through the algorithms in this chapter, it is useful to step back and assemble them into a practical toolkit. Real-world problems rarely announce which technique they require. Instead, they present constraints, equations, divisibility conditions, counting requirements, or modular arithmetic expressions. Your task is to recognize the pattern and select the appropriate tool.

This final section summarizes the essential algorithms, implementation templates, decision strategies, and practical advice that form a complete number-theoretic toolbox.

Problem

Given an arbitrary number theory problem:

prime testing
factorization
modular arithmetic
counting
congruences
divisor functions
cryptographic primitives

identify the correct algorithm and apply it efficiently.

The challenge is rarely implementing the algorithm. The challenge is knowing which algorithm to use.

Core Arithmetic Toolkit

Every number theory library should begin with a small set of foundational operations.

Greatest Common Divisor

from math import gcd

Usage:

gcd(a, b)

Applications:

coprimality
fraction reduction
modular inverses
CRT
Diophantine equations

Complexity:

O(log n)

Least Common Multiple

from math import gcd

def lcm(a, b):
    return a // gcd(a, b) * b

Applications:

periodic systems
CRT
cycle lengths
scheduling

Integer Square Root

from math import isqrt

Usage:

isqrt(n)

Applications:

trial division
perfect square detection
factorization

Never use floating-point square roots for exact integer work.

Modular Arithmetic Toolkit

Most number-theoretic algorithms eventually use modular arithmetic.

Fast Modular Exponentiation

pow(base, exponent, modulus)

Applications:

Miller-Rabin
Fermat theorem
Diffie-Hellman
RSA
modular inverses

Complexity:

O(log exponent)

Extended Euclid

def extended_gcd(a, b):
    if b == 0:
        return a, 1, 0

    g, x1, y1 = extended_gcd(b, a % b)

    return (
        g,
        y1,
        x1 - (a // b) * y1,
    )

Applications:

modular inverse
linear congruence
CRT
Diophantine equations

Modular Inverse

def mod_inverse(a, m):
    g, x, _ = extended_gcd(a, m)

    if g != 1:
        raise ValueError()

    return x % m

Applications:

division modulo m
CRT
combinatorics

Prime Toolkit

Prime operations are among the most common tasks.

Prime Sieve

def sieve(n):
    ...

Applications:

generate primes
many primality queries
prime tables

Complexity:

O(n log log n)

Smallest Prime Factor Table

spf[n]

Applications:

fast factorization
phi computation
divisor functions

Complexity:

O(n)

or:

O(n log log n)

preprocessing.

Miller-Rabin

Applications:

large primality testing
prime generation
factorization pipelines

Typical recommendation:

Use deterministic Miller-Rabin
for 64-bit integers

Factorization Toolkit

Trial Division

Use when:

n is small

Complexity:

O(√n)

SPF-Based Factorization

Use when:

many queries
small range

Complexity:

O(log n)

per query after preprocessing.

Pollard's Rho

Use when:

64-bit factorization
large composite values

Pipeline:

Miller-Rabin
+
Pollard's Rho

This combination handles most practical integer factorization tasks.

Congruence Toolkit

Linear Congruence

Problem:

ax ≡ b (mod m)

Tool:

Extended Euclid

Condition:

gcd(a,m) divides b

Chinese Remainder Theorem

Problem:

x ≡ a₁ (mod m₁)
x ≡ a₂ (mod m₂)
...

Tool:

CRT

Applications:

scheduling
modular reconstruction
parallel arithmetic

Counting Toolkit

Factorials

fact[i]

Applications:

permutations
combinations
Catalan numbers

Inverse Factorials

inv_fact[i]

Applications:

C(n,k)

queries.

Binomial Coefficients

C(n,k)
=
fact[n]
× inv_fact[k]
× inv_fact[n-k]

Complexity:

O(1)

after preprocessing.

Lucas Theorem

Use when:

n is huge
modulus is prime

Divisor Toolkit

Prime factorization unlocks many arithmetic functions.

Suppose:

n
=
p₁^e₁
p₂^e₂
...

Number of Divisors

(e₁+1)(e₂+1)...

Sum of Divisors

Π
(
p^(e+1)-1
-----------
p-1
)

Euler Phi

φ(n)
=
n Π (1 - 1/p)

Applications:

modular arithmetic
primitive roots
cryptography

Möbius Toolkit

Möbius Function

μ(n)

Applications:

inclusion-exclusion
coprime counting
divisor inversion

Möbius Inversion

Recognition pattern:

F(n)
=
Σ f(d)

Need:

f(n)

Use:

Möbius inversion

This pattern appears repeatedly in advanced counting problems.

Primitive Root Toolkit

Primitive Root Search

Applications:

finite fields
NTT
discrete logs
cryptography

Method:

1. Factor:

p−1

2. Test candidates.

3. Verify:

g^((p−1)/q) ≠ 1

for every prime factor q.

Discrete Log Toolkit

Problem:

g^x ≡ h (mod p)

Baby-Step Giant-Step

Complexity:

O(√p)

time and memory.

Use when:

moderate group size

Pollard Rho for Logs

Complexity:

O(√p)

expected time.

Memory:

O(1)

Use for larger groups.

Complexity Cheat Sheet

Task	Algorithm	Time
GCD	Euclid	O(log n)
Modular inverse	Extended Euclid	O(log n)
Modular power	Binary exponentiation	O(log e)
Prime generation	Sieve	O(n log log n)
Single primality test	Miller-Rabin	O(log³ n) bit model
Trial factorization	Trial division	O(√n)
Large factorization	Pollard's Rho	O(√p) expected
CRT	CRT	O(k log M)
Combination query	Factorial tables	O(1)
Discrete log	BSGS	O(√p)

Keep this table nearby when solving problems.

Common Recognition Patterns

"Find GCD"

Use:

Euclid

"Compute a^b mod m"

Use:

Binary exponentiation

"Is n prime?"

Use:

Sieve

or:

Miller-Rabin

depending on input size.

"Factor n"

Use:

Trial Division
SPF
Pollard's Rho

depending on constraints.

"Solve congruences"

Use:

CRT

"Count coprimes"

Use:

Euler Phi

"Recover function from divisor sums"

Use:

Möbius inversion

"Huge combination modulo prime"

Use:

factorials
inverse factorials
Lucas theorem

"Reverse exponentiation"

Use:

discrete logarithm

Recognizing these patterns is often harder than implementing the algorithms.

Building a Reusable Library

A practical number theory module typically contains:

gcd
lcm
isqrt

extended_gcd
mod_inverse
mod_pow

sieve
spf

miller_rabin
pollards_rho

crt

phi
mobius

factorials
inverse_factorials

primitive_root
discrete_log

Many competitive programming libraries, cryptographic libraries, and computer algebra systems follow this structure.

When Not to Use Number Theory

Not every problem with numbers is a number theory problem.

Examples:

array frequency counting
sorting
hashing
dynamic programming
graph search

Many beginners attempt number-theoretic solutions where a simpler algorithm is sufficient.

Always ask:

Is divisibility,
modular arithmetic,
prime structure,
or factorization
actually central?

If not, another technique may be more appropriate.

Practical Advice

Start Small

Test formulas on tiny values.

Verify Identities

Use mathematical invariants as tests.

Prefer Library Functions

Use:

pow
gcd
isqrt

before writing custom versions.

Precompute Aggressively

If many queries share the same range:

sieve
SPF
factorials

often pay for themselves.

Know Your Constraints

Input size usually determines the correct algorithm before implementation begins.

Final Example

Suppose a problem asks:

For one million queries,
compute C(n,k) mod 1,000,000,007.

Recognition:

many queries
mod prime
combinations

Toolkit selection:

factorial table
inverse factorial table
Fermat inverses

Result:

O(n) preprocessing
O(1) per query

This is exactly how number-theoretic pattern recognition saves orders of magnitude in runtime.

Takeaway

The true value of a number theory toolkit is not the individual algorithms. It is the ability to recognize which algorithm applies to a problem and how multiple algorithms fit together. Euclid solves divisibility questions, modular exponentiation handles enormous powers, CRT combines congruences, Miller-Rabin tests primality, Pollard's Rho factors large integers, Möbius inversion recovers hidden arithmetic functions, and combinatorial preprocessing turns expensive counting into constant-time queries. Together, these techniques form a practical foundation for algorithm design, cryptography, computational mathematics, and advanced programming contests.