Concepts14
Floor Sum Formula
The floor sum computes S(n,m,a,b) = sum_{i=0}^{n-1} floor((a i + b)/m) efficiently in O(log(min(a,m))) time.
Legendre's Formula
Legendre's formula gives the exponent of a prime p in n! by summing how many multiples of p, p^2, p^3, ... are ≤ n.
Harmonic Lemma
The Harmonic Lemma says that the values of \lfloor n/i \rfloor only change about 2\sqrt{n} times, so you can iterate those value blocks in O(\sqrt{n}) instead of O(n).
Inclusion-Exclusion Principle
The Inclusion-Exclusion Principle (IEP) corrects overcounting by alternately adding and subtracting sizes of intersections of sets.
Discrete Logarithm
The discrete logarithm problem asks for x such that g^x ≡ h (mod p) in a multiplicative group modulo a prime p.
Miller-Rabin Primality Test
Miller–Rabin is a fast primality test that uses modular exponentiation to detect compositeness with very high reliability.
Quadratic Residues
A quadratic residue modulo an odd prime p is any a for which x^2 ≡ a (mod p) has a solution; exactly half of the nonzero classes are residues.
Möbius Function and Inversion
The Möbius function μ(n) is 0 if n has a squared prime factor, otherwise it is (-1)^k where k is the number of distinct prime factors.
Euler's Totient Function
Euler's Totient Function φ(n) counts how many integers from 1 to n are coprime with n.
Euler's Theorem
Euler’s Theorem says that if a and n are coprime, then a raised to the power φ(n) is congruent to 1 modulo n.
Chinese Remainder Theorem
The Chinese Remainder Theorem (CRT) reconstructs an integer from its remainders modulo pairwise coprime moduli and guarantees a unique answer modulo the product.
Prime Factorization
Prime factorization expresses any integer greater than 1 as a product of primes raised to powers, uniquely up to ordering.