Math & Number Theory Essentials

Why this module exists

A surprising number of interview tasks hide in basic number theory: gcd/lcm, modular arithmetic, fast exponentiation, and prime sieves. These are small building blocks that unlock larger problems.

GCD and LCM

• GCD: greatest common divisor (Euclid's algorithm)
• LCM: least common multiple

Formula: lcm(a, b) = a / gcd(a, b) * b

Use 64-bit to avoid overflow while multiplying.

Modular arithmetic

Key rules:

• (a + b) % m = ((a % m) + (b % m)) % m
• (a * b) % m = ((a % m) * (b % m)) % m

Modular arithmetic powers hashing, crypto, and combinatorics.

Fast exponentiation (binary exponentiation)

Compute a^b mod m in O(log b):

• If b is odd, multiply result by a
• Square a each step
• Shift b right

Sieve of Eratosthenes

To count primes up to N:

1. Mark all as prime
2. For each p up to sqrt(N), mark multiples

Time: O(n log log n). Space: O(n).

What you will build

• GCD + LCM over an array.
• Fast modular exponentiation.
• Prime counting with a sieve.