18.22 Practical Number Theory Patterns
Throughout this chapter we studied individual algorithms: - Euclidean Algorithm - Modular Arithmetic - Fast Exponentiation
18.22 Practical Number Theory Patterns
Throughout this chapter we studied individual algorithms:
- Euclidean Algorithm
- Modular Arithmetic
- Fast Exponentiation
- Sieve Methods
- Chinese Remainder Theorem
- Euler Phi
- Primitive Roots
- Miller-Rabin
- Pollard's Rho
- Möbius Inversion
In real systems, however, these algorithms rarely appear in isolation. Practical number theory is about recognizing recurring patterns and selecting the right combination of tools.
This section serves as a cookbook of common problem types, showing how experienced practitioners decompose problems into reusable number-theoretic building blocks.
Problem
Given an unfamiliar number theory problem:
count
optimize
factor
test
construct
enumerate
identify the appropriate algorithmic pattern.
The goal is not memorization. The goal is developing instinct.
Pattern 1: Repeated GCD Queries
Problem:
Many gcd computations
Example:
Find gcd for one million pairs.
Use:
Euclidean Algorithm
Implementation:
from math import gcd
def batch_gcd(pairs):
return [gcd(a, b) for a, b in pairs]
Complexity:
O(log min(a,b))
per query.
The Euclidean Algorithm is almost always optimal.
Pattern 2: Repeated Prime Queries
Problem:
Is x prime?
for many values.
Small range:
x ≤ 10^7
Use:
Sieve of Eratosthenes
Large isolated values:
64-bit integers
Use:
Miller-Rabin
Decision rule:
| Situation | Tool |
|---|---|
| Many small queries | Sieve |
| One large query | Miller-Rabin |
| Factorization needed too | SPF sieve |
Pattern 3: Fast Factorization
Problem:
Factor n
Use:
Trial Division
if:
n < 10^6
Use:
SPF Table
for many queries.
Use:
Pollard's Rho
+
Miller-Rabin
for large integers.
Typical modern workflow:
Input
↓
Miller-Rabin
↓
Prime?
↓
Pollard's Rho
↓
Recurse
This is the standard 64-bit factorization pipeline.
Pattern 4: Huge Powers Modulo m
Problem:
a^b mod m
Use:
Binary Exponentiation
Never compute:
a ** b
directly.
Instead:
pow(a, b, m)
Complexity:
O(log b)
This is one of the most important optimization patterns in computational mathematics.
Pattern 5: Modular Division
Problem:
a / b mod m
Question:
Does b have an inverse?
Check:
gcd(b,m)
Cases:
gcd(b,m)=1
Use:
Extended Euclid
or:
b^(m−2)
if m is prime.
Otherwise:
inverse may not exist
Always verify invertibility before dividing.
Pattern 6: Multiple Congruences
Problem:
x ≡ a₁ (mod m₁)
x ≡ a₂ (mod m₂)
...
Use:
Chinese Remainder Theorem
If moduli are pairwise coprime:
unique solution modulo product
If not:
check compatibility
via:
gcd(mᵢ,mⱼ)
CRT is often the hidden solution in scheduling and synchronization problems.
Pattern 7: Count Coprime Values
Problem:
How many numbers ≤ n are coprime to n?
Use:
Euler Phi Function
Compute:
φ(n)
via factorization.
Example:
φ(36)=12
This pattern appears frequently in modular arithmetic and cryptography.
Pattern 8: Count Multiples with Inclusion-Exclusion
Problem:
Count numbers divisible by
2 or 3 or 5
Use:
Inclusion-Exclusion
Example:
count(2)
+
count(3)
+
count(5)
-
count(6)
-
count(10)
-
count(15)
+
count(30)
When divisor sums become complicated:
Möbius inversion
often generalizes the idea.
Pattern 9: Recover Original Function from Divisor Sums
Problem:
F(n)=Σ f(d)
Need:
f(n)
Use:
Möbius Inversion
Recognition clue:
sum over divisors
Many advanced counting problems reduce to this transformation.
Pattern 10: Compute Many Prime Factors
Problem:
Factor all numbers up to n
Use:
Smallest Prime Factor Sieve
Example:
spf[x]
stores the smallest prime divisor.
Benefits:
Factorization:
O(log n)
after preprocessing.
This is a common competitive-programming technique.
Pattern 11: Large Combination Queries
Problem:
C(n,k) mod p
for many queries.
Use:
factorial table
inverse factorial table
Example:
C(n,k)
=
fact[n]
× inv_fact[k]
× inv_fact[n-k]
Complexity:
O(1)
per query after preprocessing.
This pattern appears constantly in counting problems.
Pattern 12: Massive Exponents
Problem:
a^(huge number) mod n
Use:
Euler's theorem
or:
Fermat's theorem
to reduce exponents.
Example:
7^1000000 mod 13
Since:
φ(13)=12
reduce:
1000000 mod 12
first.
The exponent often collapses dramatically.
Pattern 13: Generate All Primes
Problem:
List primes ≤ n
Use:
Sieve of Eratosthenes
Complexity:
O(n log log n)
For very large ranges:
Segmented Sieve
This is usually the fastest approach.
Pattern 14: Detect Perfect Powers
Problem:
n = a^k ?
Use:
Prime factorization
Compute exponent GCD.
Example:
216
=
2^3 × 3^3
Exponent GCD:
3
Therefore:
216 = 6^3
Factorization often simplifies these problems dramatically.
Pattern 15: Find Generators
Problem:
Generate all nonzero residues
Use:
Primitive Roots
Factor:
p−1
and test candidates.
Applications:
Diffie-Hellman
NTT
Discrete logs
Pattern 16: Reverse Exponentiation
Problem:
g^x ≡ h (mod p)
Need:
x
Use:
Discrete Logarithm
For moderate sizes:
Baby-Step Giant-Step
Complexity:
O(√p)
This is the inverse of modular exponentiation.
Pattern 17: Fast Polynomial Multiplication
Problem:
Multiply huge polynomials
Use:
FFT
or:
NTT
NTT requires:
prime modulus
primitive root
This is a direct application of modular arithmetic and primitive roots.
Pattern 18: Cryptographic Prime Generation
Problem:
Generate a large prime
Workflow:
Generate random odd candidate
↓
Small prime filtering
↓
Miller-Rabin
↓
Accept if prime
This is how many cryptographic systems generate primes.
Pattern 19: Large Rational Arithmetic
Problem:
Repeated fractions
Always reduce using:
gcd(numerator, denominator)
Example:
g = gcd(num, den)
num //= g
den //= g
Failure to simplify often causes explosive growth.
Pattern 20: Unknown Number Theory Problem
When facing a new problem, ask:
Is this about divisors?
Think:
factorization
phi
mobius
Ask:
Is this about powers?
Think:
binary exponentiation
Euler
Fermat
Ask:
Is this about congruences?
Think:
CRT
linear congruence
modular inverse
Ask:
Is this about primes?
Think:
sieve
Miller-Rabin
Pollard's Rho
Most number theory problems eventually reduce to one of these categories.
Decision Tree
A useful mental model:
Prime?
│
├─ Many values → Sieve
└─ One large value → Miller-Rabin
Factor?
│
├─ Many values → SPF
├─ Small value → Trial Division
└─ Large value → Pollard's Rho
Power?
│
├─ Normal → Binary Exponentiation
└─ Huge exponent → Euler/Fermat reduction
Congruence?
│
├─ One equation → Extended Euclid
└─ Many equations → CRT
Counting?
│
├─ Combinations → Factorials
├─ Coprime counts → Phi
└─ Divisor sums → Möbius
Experienced problem solvers often follow this reasoning almost automatically.
Common Mistakes
Using Advanced Tools Too Early
Trial division is often sufficient.
Do not start with Pollard's Rho for tiny inputs.
Ignoring Constraints
Algorithm choice should be driven by:
input size
query count
memory limits
Forgetting Precomputation
Repeated work often dominates runtime.
Treating Number Theory as Memorization
Focus on patterns rather than formulas.
Missing Hidden Structure
Many problems disguise:
CRT
phi
factorization
behind application-specific wording.
Testing Your Pattern Recognition
When you see:
Find gcd(a,b)
immediately think:
Euclid
When you see:
a^b mod m
think:
Binary Exponentiation
When you see:
Many primality queries
think:
Sieve
When you see:
One huge primality query
think:
Miller-Rabin
When you see:
Recover function from divisor sums
think:
Möbius inversion
The faster these associations become, the easier number theory problems feel.
Takeaway
Practical number theory is less about individual formulas and more about recognizing recurring patterns. GCD problems suggest Euclid, modular powers suggest binary exponentiation, repeated prime queries suggest sieves, congruence systems suggest CRT, divisor sums suggest Möbius inversion, and large factorization tasks suggest Miller-Rabin combined with Pollard's Rho. As you gain experience, the challenge shifts from implementing algorithms to identifying which algorithmic pattern a problem is hiding. This pattern-recognition skill is what transforms a collection of techniques into a working number-theory toolkit.