Number Theory: GCD, Primes, and Modular Arithmetic

The interview-relevant slice of number theory: reduce with gcd, test and list primes, and keep huge answers small with a modulus. Use // (integer division, 7 // 2 == 3) and % (remainder), never / (float, 7 / 2 == 3.5) where a whole number is needed.

GCD and LCM

• gcd(a, b) = largest number dividing both. Euclid: replace (a, b) with (b, a % b) until b == 0; the last a is the answer. Works because any divisor of a and b also divides a % b.
• Iterative: while b: a, b = b, a % b; return a. Recursive: gcd(a, 0) = a, else gcd(b, a % b).
• gcd == 1 means coprime. gcd(a, 0) == a.
• lcm(a, b) = a // gcd(a, b) * b. Divide before multiplying so the intermediate stays small (avoids overflow in fixed-width languages).
• Time O(log(min(a, b))), space O(1).

Primality (trial division)

• Prime = integer > 1 divisible only by 1 and itself.
• Test divisors only up to sqrt(n): factors pair up as d and n // d, and one of each pair is <= sqrt(n).
• Loop while i * i <= n (integer test, no float sqrt); handle n < 2, 2, evens; step odd i by 2.
• Time O(sqrt(n)), space O(1).

Sieve of Eratosthenes

• All primes up to n: mark each prime’s multiples as composite; whatever stays True is prime.
• Start crossing out at i * i (smaller multiples already crossed out by smaller factors); outer loop only to sqrt(n).
• Mark is_p[0] = is_p[1] = False.
• Time O(n log log n), space O(n). Use for many primes / many checks under a limit; trial division for one isolated number.

is_p = [True] * (n + 1); is_p[0] = is_p[1] = False
i = 2
while i * i <= n:
    if is_p[i]:
        for j in range(i * i, n + 1, i):  # start at i*i
            is_p[j] = False
    i += 1

Modular arithmetic

• Answers “modulo 1_000_000_007” (a large prime): return the remainder so numbers stay small and fit fixed-width ints.
• (a + b) % m == ((a % m) + (b % m)) % m; same for *. So reduce as you go, after each step, not just at the end.
• Python’s % is always non-negative: -7 % 3 == 2, so subtraction-then-% m needs no fixup.
• Fast power: pow(base, exp, mod) computes base**exp % mod in O(log exp) via square-and-multiply (square repeatedly, multiply in the powers whose binary bit is set, reduce each step). Modular inverse under prime m: pow(a, m - 2, m).

Pitfalls

• / vs //: / gives a float; use // for indexes and exact counts.
• Forgetting to % m intermediate products (overflow in fixed-width languages).
• Sieve starting at 2 * i (redundant) or forgetting to mark 0/1.
• Primality with i <= n ** 0.5 (float rounding); use i * i <= n.

Summary table