Math basics: GCD, primes & modular arithmetic

The greatest common divisor of two numbers is the largest number that divides both: gcd(12, 18) = 6. Trying every candidate is slow. Euclid's algorithm uses one fact: any number that divides a and b also divides a mod b, the remainder, and the other way round. So gcd(a, b) = gcd(b, a mod b), and the pair shrinks until the remainder is 0. The other number is then the answer.

Every two rounds the larger number at least halves, so the number of rounds is O(log(min(a, b))): fewer than 90 rounds for numbers up to 10¹⁸.

The least common multiple, the smallest number both divide, follows from it: lcm(a, b) = a ÷ gcd(a, b) × b. Divide before multiplying so the intermediate value stays small.

A prime number is a whole number above 1 whose only divisors are 1 and itself: 2, 3, 5, 7, 11. To test one number n, try dividing by 2, 3, 4, … up to √n: if n = a × b, one of a and b is at most √n. That is O(√n) per number.

To find every prime below n at once, the sieve of Eratosthenes is much faster. Mark every number as a candidate. Take the smallest unmarked-out number, which must be prime, and cross out all its multiples. Repeat. Two details make it quick:

• start crossing at p × p: every smaller multiple of p has a smaller prime factor and is already crossed out;
• stop once p × p reaches n: anything still marked is prime.

Each prime p crosses out about n ÷ p numbers, and those sums add up to O(n log log n), close to linear. The cost is O(n) memory for the marks.

Answers that count ways or arrangements grow far past what a 64-bit integer holds, so problems ask for the answer mod some m, often 10⁹ + 7. Modular arithmetic works with remainders only, using rules that let you reduce at every step:

• (a + b) mod m = ((a mod m) + (b mod m)) mod m
• (a × b) mod m = ((a mod m) × (b mod m)) mod m
• (a − b) mod m: add m before taking the remainder, since some languages give negative remainders.

Division has no such rule: dividing mod m needs a modular inverse, a topic of its own.

Reducing after every operation keeps every value below m. With m near 10⁹, the product of two remainders is below about 10¹⁸, which fits in a signed 64-bit integer. JavaScript numbers are exact only up to 2⁵³, about 9 × 10¹⁵, so there such products need BigInt.

Computing x to the power e by multiplying e times is O(e), hopeless for e = 10¹⁸. Fast exponentiation reads e in binary. 217 is 11011001, so 3²¹⁷ = 3¹²⁸ × 3⁶⁴ × 3¹⁶ × 3⁸ × 3¹. Squaring gives 3¹, 3², 3⁴, 3⁸ and so on, one square per bit, and the result multiplies in the squares whose bit is 1. Mod m after every multiplication keeps the numbers small.

One squaring per bit of e and at most one multiplication: O(log e). The same loop computes huge powers mod 10⁹ + 7, matrix powers, and the modular inverse when m is prime.