Groups
Category
Level
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 gives the exponent of a prime p in n! by summing how many multiples of p, p^2, p^3, ... are โค n.
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).
The Inclusion-Exclusion Principle (IEP) corrects overcounting by alternately adding and subtracting sizes of intersections of sets.
The discrete logarithm problem asks for x such that g^x โก h (mod p) in a multiplicative group modulo a prime p.
MillerโRabin is a fast primality test that uses modular exponentiation to detect compositeness with very high reliability.
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.
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 ฯ(n) counts how many integers from 1 to n are coprime with n.
Eulerโs Theorem says that if a and n are coprime, then a raised to the power ฯ(n) is congruent to 1 modulo n.
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 expresses any integer greater than 1 as a product of primes raised to powers, uniquely up to ordering.