Mathematics
Divisibility, remainders and counting: the arithmetic that has to stay fast and stay inside a machine word.
Number Theory Basics: Adding on a clock of 12
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
In this order
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.