Mathematics
Divisibility, remainders and counting: the arithmetic that has to stay fast and stay inside a machine word.
Number theory in an algorithms course comes down to two operations: dividing with a remainder, and multiplying under a modulus. Euclid's algorithm replaces the pair (a, b) with (b, a mod b) and reaches the gcd in O(log min(a, b)) steps, because two rounds of that at least halve the larger number. Extended Euclid, the modular inverse and lcm are all built on that one step.
Modular arithmetic is what stops numbers overflowing. Reduce after every operation and no intermediate value ever passes m, which is why a^b mod m is computed by squaring once per bit of b instead of forming a^b first. Division has no direct counterpart: dividing by a means multiplying by its inverse, which exists only when a and m share no factor, and is found by extended Euclid or by a^(m-2) when m is prime.
The other half is bulk precomputation and counting. A sieve crosses out the multiples of each prime and hands you every prime below n in O(n log log n), far cheaper than testing n numbers one at a time at O(sqrt(n)) each. Pascal's triangle produces every C(n, k) by addition alone, which matters because 21! already overflows a 64-bit integer while C(21, 10) fits easily.
After this you can
- Compute gcd, lcm and a modular inverse, and say when each one fails to exist
- Reduce under a modulus so that no intermediate product ever overflows
- Choose between trial division, a full sieve and a segmented sieve by the range you need
- Raise a number to a large power in O(log e) multiplications
- Compute binomial coefficients without ever forming a factorial
One step to 4.
In this order
- Modular ArithmeticArithmetic on a clock with m positions. Reduce at every step and nothing ever grows past m.
- Greatest Common DivisorThe largest number that divides both. Euclid finds it in O(log n) steps.
- Euclidean AlgorithmReplace (a, b) with (b, a mod b) until b is 0. The last non-zero value is the gcd.
- Least Common Multiplelcm(a, b) = a * b / gcd(a, b).
- Primality TestTry each divisor up to the square root. No hit means prime.
- Prime FactorizationDivide out each candidate while it divides. Whatever is left above 1 is prime.
- Sieve of EratosthenesMark multiples of each prime; what survives is prime.
- Fast ExponentiationSquare the base once per bit of the exponent, and multiply in on every 1 bit.
- Fermat's Little TheoremFor prime p and a not divisible by p, a^(p-1) = 1 mod p.
- Extended Euclidean AlgorithmAlso finds x, y with ax + by = gcd(a, b) by carrying coefficients back up the division table; the route to modular inverses.
- Modular Inversex with ax = 1 mod m; via extended Euclid, or a^(m-2) when m is prime.
- Pascal's TriangleEach entry is the sum of the two above it; row n holds C(n, k).
- CombinationsC(n, k) = n! / (k! (n-k)!); computed safely via Pascal's rule or multiplicative formula.
Also in this category
Number Theory
Where people go wrong
Overflow between the reductions
a * b mod m is only safe when a * b itself fits. With 64-bit integers and m near 10^18 the product wraps before the mod is applied, and the result is wrong without any error being raised; that is what the doubling form of modular multiplication is for.
lcm by multiplying first
lcm(a, b) = a * b / gcd(a, b) overflows for large a and b even when the answer itself fits comfortably. Divide before you multiply: a / gcd(a, b) * b.
An inverse that does not exist
a has an inverse mod m only when gcd(a, m) = 1, and the a^(m-2) shortcut is an inverse only when m is prime. Use Fermat's route with a composite modulus and you get a number back, just not the right one.
Or a different category
Bit Manipulation
The question is about the bits of a number rather than its value: masks, parity, powers of two.
Computational Geometry
The numbers are coordinates, so the arithmetic is about orientation and distance rather than divisibility.