Number Theory & Algebra
Divisibility, primes, modular arithmetic and the bit tricks behind many olympiad problems.
29 articles~180 min total
0/29
Fundamentals
- Binary ExponentiationCompute powers in O(log n) multiplications by squaring, and reuse the same trick for modular powers, matrices and more.8 minBeginner
- Euclidean Algorithm (GCD and LCM)Compute the greatest common divisor in O(log min(a, b)) steps, derive the LCM from it, and learn the modulo-free binary variant.5 minBeginner
- Extended Euclidean AlgorithmFind integers x and y with ax + by = gcd(a, b), and use them to solve linear Diophantine equations.5 minIntermediate
- Fibonacci NumbersProperties of Fibonacci numbers and four ways to compute F(n): linear, matrix power, fast doubling and modulo-p with the Pisano period.6 minIntermediate
- Linear Diophantine EquationsSolve ax + by = c in integers: existence, one solution, all solutions, solutions in a range, and the solution with the smallest x + y.7 minIntermediate
Prime numbers
- Sieve of EratosthenesFind all primes up to n in O(n log log n), then make it fast in Python with slice assignment, and extend it to segments and smallest prime factors.8 minBeginner
- Primality TestsDecide whether a single large number is prime: trial division, the Fermat test, and the deterministic Miller-Rabin test for 64-bit integers.6 minIntermediate
- Integer FactorizationBreak a number into primes with trial division, a smallest-prime-factor sieve, Fermat's method and Pollard's rho for numbers up to 10^18 and beyond.10 minAdvanced
- Linear Sieve and Multiplicative FunctionsThe O(n) sieve, and how to compute φ, μ, d and σ for every number up to n in one pass.5 minAdvanced
Number-theoretic functions
- Euler's Totient FunctionCount the integers up to n that are coprime to n, compute φ(n) from the factorization or for all n at once, and apply Euler's theorem.5 minIntermediate
- Number and Sum of DivisorsCompute d(n) and σ(n) from the prime factorization, list all divisors in O(√n), and get them for every n up to N with a sieve.4 minIntermediate
Modular arithmetic
- Modular Multiplicative InverseDivide under a modulus. Find a^-1 mod m with extended Euclid, with Fermat/Euler, with Python's pow, and for a whole array at once.5 minIntermediate
- Chinese Remainder TheoremCombine congruences x ≡ a_i (mod m_i) into a single one, first for coprime moduli, then for arbitrary moduli.4 minAdvanced
- Linear Congruence EquationSolve a·x ≡ b (mod n): when solutions exist, how many there are, and how to list them.3 minIntermediate
- Garner's AlgorithmRecover a big number from its residues modulo pairwise coprime primes using a mixed radix representation, without big-integer arithmetic.4 minAdvanced
- Factorial Modulo a PrimeCompute n! mod p for a small prime p and huge n by Wilson's theorem, and find the exponent of p in n!.4 minAdvanced
- Discrete LogarithmSolve a^x ≡ b (mod m) with baby-step giant-step in O(√m), including the case where a and m are not coprime.6 minAdvanced
- Primitive RootsFind a generator of the multiplicative group modulo n: when it exists, how to test a candidate, and how many there are.4 minAdvanced
- Discrete RootSolve x^k ≡ a (mod n) by moving to exponents with a primitive root and a linear congruence.4 minAdvanced
- Montgomery MultiplicationMultiply modulo n without dividing by n, by working in a representation where division is a bit shift.5 minAdvanced
Number systems
- Balanced TernaryRepresent integers with digits −1, 0, 1: no sign needed, and rounding is free.4 minIntermediate
- Gray CodeOrder all n-bit numbers so that neighbours differ in exactly one bit; conversions in both directions and where it is used.4 minIntermediate
- Continued FractionsWrite a number as a ladder of integers a₀ + 1/(a₁ + 1/(a₂ + …)), compute convergents and best rational approximations, and connect them to the Stern-Brocot tree and floor sums.11 minAdvanced
Bits
- Bit ManipulationBinary numbers, bitwise operators, the classic tricks (lowest set bit, popcount, powers of two) and how to iterate over subsets with masks.6 minIntermediate
- Enumerating Submasks of a BitmaskVisit all submasks of every mask in total 3ⁿ steps, and compute sums over subsets or supersets in O(n·2ⁿ).5 minAdvanced
Big numbers and polynomials
- Fast Fourier Transform and Number Theoretic TransformMultiply polynomials and big numbers in O(n log n): the complex FFT, the exact NTT modulo 998244353, arbitrary moduli, and a big-integer shortcut that is uniquely fast in Python.14 minAdvanced
- Arbitrary-Precision ArithmeticHow big integers work inside: digit arrays, schoolbook and Karatsuba multiplication, and what Python's int already gives you.9 minIntermediate
- Operations on Polynomials and Power SeriesFast inverse, division, logarithm, exponential and powers of polynomials with Newton's method, plus multipoint evaluation, interpolation and GCD.13 minAdvanced