Concepts10
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.
Miller-Rabin Primality Test
MillerβRabin is a fast primality test that uses modular exponentiation to detect compositeness with very high reliability.
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.
Extended Euclidean Algorithm
The Extended Euclidean Algorithm finds integers x and y such that ax + by = gcd(a, b) while also computing gcd(a, b).
GCD and Euclidean Algorithm
The greatest common divisor (gcd) of two integers is the largest integer that divides both without a remainder.