Groups
Category
Level
A derangement is a permutation with no element left in its original position, often written as !n or D(n).
Lucas' Theorem lets you compute C(n, k) modulo a prime p by working digit-by-digit in base p.
The Inclusion-Exclusion Principle (IEP) corrects overcounting by alternately adding and subtracting sizes of intersections of sets.
A linear Diophantine equation ax + by = c has integer solutions if and only if gcd(a, b) divides c.
The binomial theorem expands (x + y)^n into a sum of terms using binomial coefficients that count how many ways to choose k items from n.
Stars and Bars counts the ways to distribute n identical items into k distinct bins using combinations.
A primitive root modulo n is a number g that cycles through all units modulo n when you repeatedly multiply by g, so its multiplicative order equals \(\varphi(n)\).
The discrete logarithm problem asks for x such that g^x ≡ h (mod p) in a multiplicative group modulo a prime p.
Pollard's Rho is a randomized algorithm that finds a non-trivial factor of a composite integer by walking a pseudorandom sequence modulo n and extracting a factor with a gcd.
Miller–Rabin is a fast primality test that uses modular exponentiation to detect compositeness with very high reliability.
Permutations count ordered selections, while combinations count unordered selections.
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.