Number theory
Number theory studies whole numbers: which numbers divide which, and what remains after a division. In competitive programming it comes up in problems about fractions and periods, and whenever the answer is asked modulo a large prime.
The Euclidean algorithm finds the greatest common divisor (GCD) of two whole numbers: the largest number that divides both with nothing left over.
Modular arithmetic computes the remainder of a sum, a difference, a product or a power after dividing by some number m, without ever computing the huge number itself. You need it whenever a problem says "print the answer modulo 10^9 + 7". If the problem needs all the digits of the huge number, use big integers instead.
Binary exponentiation computes a power such as 3^{13}, or its remainder after dividing by 10^9 + 7, with at most two multiplications per binary digit of the exponent instead of one multiplication per factor. It is the standard tool when a problem asks for a power with an exponent up to 10^9 or 10^{18}.
A primality test decides whether a number is prime: greater than 1, with no divisors other than 1 and itself. Trial division, the test in this article, needs at most about 10^6 tries for one number up to 10^{12}. To find every prime in a range, use the sieve of Eratosthenes instead.
The extended Euclidean algorithm finds the greatest common divisor of two numbers and together with integers and such that a \cdot x + b \cdot y = g. With them you can solve equations such as 75x + 21y = 12 in integers and divide modulo any number. If you only need the GCD, the Euclidean algorithm is enough.
The modular inverse of a number modulo is the number that undoes multiplying by . It is how you divide when a problem asks for the answer modulo a prime such as 10^9 + 7. If the modulus is not prime, find the inverse with the extended Euclidean algorithm instead.
The sieve of Eratosthenes finds all prime numbers up to n. A prime is a number greater than 1 whose only divisors (numbers that divide it with no remainder) are 1 and itself; 1 is not prime. The sieve is for questions about many numbers in one range, up to about 10^7. To check one large number, try its divisors instead, as the primality test does.
Prime factorization writes a number as a product of primes, such as 60 = 2 · 2 · 3 · 5. A prime is a number greater than 1 whose only divisors are 1 and itself; 1 is not prime. Every number greater than 1 has exactly one such product, up to the order of the factors. Trial division factors one number up to about 10^{12} in about 10^6 tries, and the smallest-prime-factor array factors many numbers up to about 10^7.
A divisor of a number n is a number from 1 to n that divides n with no remainder, such as 4 for 12. All divisors of a number up to about 10^{12} can be listed with about 10^6 tries, by going only up to its square root. The number and the sum of the divisors also follow from the prime factorization without listing them, and a different loop finds the divisors of every number up to about 10^6 at once. To split a number into primes instead, see prime factorization.
Euler's totient function φ(n) (read "phi of n") counts the integers from 1 to n that are coprime to n: they share no divisor with n except 1. It answers problems that count irreducible fractions with denominator n, or step sizes k that visit every cell of a cycle of length n, for one n up to about 10^{12} or for all n up to about 10^7. To count coprime numbers in another range, use inclusion–exclusion instead.