EP Ethan Pham Project Euler, competitive programming, and notes on the things I keep studying.
Data Structures & Algorithms

Number Theory

These notes emphasize the parts of number theory that become algorithms rather than standalone proofs.

12 published notes
4 planned topics
6 advanced or expert notes
basic starting level
Back to DSA Competitive Programming
Category Overview

Number Theory

Modular arithmetic, multiplicative structure, and fast polynomial machinery.

Raw TeX

Overview

Number theory in contest problems is less about memorizing isolated theorems and more about recognizing structure: modular inverses, multiplicative functions, convolution-friendly moduli, or the shape of a factorization argument.

What These Notes Emphasize

I prefer explanations that connect the algebra to the implementation. If a fact is only useful after it becomes a linear sieve, a CRT merge, or an NTT butterfly, the note should say so directly.

Difficulty Bands

How this branch is distributed

The labels are not cosmetic. They are there to signal the amount of prerequisite structure and implementation fragility you should expect before opening the note.

basic: 5 intermediate: 1 advanced: 6 expert: 0
5 basic
basic

These are the shortest on-ramp notes in this category and the ones most likely to be usable immediately in contest practice.

GCD and Extended Euclid, Modular Arithmetic, Modular Inverse, Sieve of Eratosthenes, Prime Factorization

1 intermediate
intermediate

These notes assume the base routine is already familiar and focus on the first real structural upgrades.

Euler Phi

6 advanced
advanced

These are the notes where proofs, reductions, or implementation details become the main bottleneck.

Chinese Remainder Theorem, Mobius Function, NTT, Primitive Roots and Discrete Logarithm, Miller-Rabin and Pollard Rho, Polynomial Interpolation

Published notes

What is already written

These are the finished note pages in this category, each with rendered TeX, C++ code, references, and practice suggestions.

01
basic

GCD and Extended Euclid

The basic divisibility toolkit for reducing fractions, solving linear equations, and building modular arithmetic routines.

gcd extended euclid / diophantine equations
02
basic

Modular Arithmetic

Keep arithmetic safe under a modulus by tracking the algebraic rules that still survive after reduction.

mod algebra / implementation
03
basic

Modular Inverse

Undo multiplication modulo m when the gcd condition allows it, and choose the right inverse routine for the modulus.

modular arithmetic inverse / extended euclid
04
basic

Sieve of Eratosthenes

Precompute primality and smallest prime factors once, then answer many prime-related queries cheaply.

primes preprocessing / smallest prime factor
05
advanced

Chinese Remainder Theorem

Combine modular constraints into one congruence when the residue classes are compatible.

CRT congruences / extended euclid
06
basic

Prime Factorization

Break numbers into prime powers and choose the right factorization strategy for the size and query pattern.

primes factorization / divisors
07
intermediate

Euler Phi

Count how many integers up to n are coprime to n, and use the factorization formula to turn that count into code.

coprimality multiplicative function / totient
08
advanced

Mobius Function

Use the Mobius function and inversion to separate exact divisibility structure from overcounted multiples.

mobius inversion / sieve
09
advanced

NTT

Polynomial convolution modulo 998244353 using roots of unity and iterative butterfly layers.

convolution polynomials / modular arithmetic
010
advanced

Primitive Roots and Discrete Logarithm

Work inside cyclic multiplicative groups by finding generators and solving exponent equations with baby-step giant-step.

cyclic groups bsgs / modular arithmetic
011
advanced

Miller-Rabin and Pollard Rho

The standard 64-bit primality and factorization toolkit once trial division stops being realistic.

primality factorization / randomized
012
advanced

Polynomial Interpolation

Recover or evaluate a low-degree polynomial from sample points, usually with modular Lagrange interpolation.

polynomials lagrange / mod
Study Order

Recommended order to read this branch

The default order follows each note's dependency weight: early notes establish primitives, later notes reuse them or assume the same invariants without re-explaining them.

01
basic

GCD and Extended Euclid

The basic divisibility toolkit for reducing fractions, solving linear equations, and building modular arithmetic routines.

gcd extended euclid / diophantine equations
02
basic

Modular Arithmetic

Keep arithmetic safe under a modulus by tracking the algebraic rules that still survive after reduction.

mod algebra / implementation
03
basic

Modular Inverse

Undo multiplication modulo m when the gcd condition allows it, and choose the right inverse routine for the modulus.

modular arithmetic inverse / extended euclid
04
basic

Sieve of Eratosthenes

Precompute primality and smallest prime factors once, then answer many prime-related queries cheaply.

primes preprocessing / smallest prime factor
05
advanced

Chinese Remainder Theorem

Combine modular constraints into one congruence when the residue classes are compatible.

CRT congruences / extended euclid
06
basic

Prime Factorization

Break numbers into prime powers and choose the right factorization strategy for the size and query pattern.

primes factorization / divisors
07
intermediate

Euler Phi

Count how many integers up to n are coprime to n, and use the factorization formula to turn that count into code.

coprimality multiplicative function / totient
08
advanced

Mobius Function

Use the Mobius function and inversion to separate exact divisibility structure from overcounted multiples.

mobius inversion / sieve
09
advanced

NTT

Polynomial convolution modulo 998244353 using roots of unity and iterative butterfly layers.

convolution polynomials / modular arithmetic
010
advanced

Primitive Roots and Discrete Logarithm

Work inside cyclic multiplicative groups by finding generators and solving exponent equations with baby-step giant-step.

cyclic groups bsgs / modular arithmetic
011
advanced

Miller-Rabin and Pollard Rho

The standard 64-bit primality and factorization toolkit once trial division stops being realistic.

primality factorization / randomized
012
advanced

Polynomial Interpolation

Recover or evaluate a low-degree polynomial from sample points, usually with modular Lagrange interpolation.

polynomials lagrange / mod
Planned topics

Next topics in this branch

These are still intentionally shown as planned or outline topics rather than shallow filler. The branch should feel incomplete in honest places instead of fake-complete everywhere.

Inclusion-exclusion planned Garner algorithm outline Multiplicative functions outline Berlekamp-Massey outline
Resources

Source Files and Assets

Raw files are still available here when you want the original TeX, C++, or statement assets.

Show raw files
Category TeX sourcecompetitive_programming/dsa/number-theory/index.tex