Concepts38
Modular Inverse
A modular inverse of a modulo m is a number a_inv such that a Γ a_inv β‘ 1 (mod m).
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.
Fermat's Little Theorem
Fermat's Little Theorem says that for a prime p and integer a not divisible by p, a^{p-1} β‘ 1 (mod p).
Fast Exponentiation
Fast exponentiation (binary exponentiation) computes a^n using repeated squaring in O(log n) multiplications.
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.
Linear Sieve
The linear sieve builds all primes up to n in O(n) time by ensuring each composite is marked exactly once by its smallest prime factor (SPF).
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).
Sieve of Eratosthenes
The Sieve of Eratosthenes marks multiples of each prime to find all primes up to n in O(n log log n) time.
GCD and Euclidean Algorithm
The greatest common divisor (gcd) of two integers is the largest integer that divides both without a remainder.
Linear Basis for XOR
A linear basis for XOR is a compact set of at most W numbers (W = number of bits) that can generate every XOR value obtainable from a multiset of numbers.
Matrix Rank and Linear Independence
Matrix rank is the number of pivots after Gaussian elimination and equals the dimension of both the column space and the row space.