Math for Coding Interviews: GCD, Primes, Modular Arithmetic

Coding interviews are not math contests, but a small toolkit of number theory pays for itself many times over. GCD, primes, and modular arithmetic appear in problems about fractions, periodicity, hashing, combinatorics modulo a prime, and any “answer modulo 10^9 + 7” question. This article covers the algorithms that come up most often, with code and the reasoning behind their complexities.

GCD with the Euclidean algorithm

The greatest common divisor of a and b is the largest integer that divides both. The Euclidean algorithm uses the identity gcd(a, b) = gcd(b, a mod b), which is true because any divisor of a and b also divides their remainder.

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

Each step reduces the pair by at least a factor of phi (the golden ratio) every two iterations, so the algorithm runs in O(log min(a, b)) time. Python’s math.gcd is implemented exactly this way.

The least common multiple falls out of GCD with no extra work:

def lcm(a, b):
    return a // gcd(a, b) * b

Order of operations matters: divide first to avoid overflow in languages without arbitrary precision.

Extended Euclidean algorithm

The extended version also produces integers x, y such that a*x + b*y = gcd(a, b). This is the foundation for modular inverses when the modulus is not prime.

def extended_gcd(a, b):
    if b == 0:
        return a, 1, 0
    g, x1, y1 = extended_gcd(b, a % b)
    return g, y1, x1 - (a // b) * y1

If gcd(a, m) == 1, then x mod m is the modular inverse of a modulo m. Otherwise, no inverse exists.

Primes with the sieve of Eratosthenes

Trial division checks divisibility up to sqrt(n) and runs in O(sqrt(n)) per test, fine for occasional checks. When you need every prime up to n, the sieve of Eratosthenes generates them all in O(n log log n) time and O(n) space.

def sieve(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(n ** 0.5) + 1):
        if is_prime[i]:
            for j in range(i * i, n + 1, i):
                is_prime[j] = False
    return [i for i, p in enumerate(is_prime) if p]

Two optimizations worth knowing:

• Start the inner loop at i * i. Smaller multiples are already crossed off by earlier primes.
• Use a bytearray or bitarray instead of a list of booleans to cut memory by 8x or more.

A linear sieve runs in O(n) by ensuring each composite is crossed off exactly once by its smallest prime factor. It is more code and only worth it for very large n.

Modular exponentiation

Compute a^e mod m efficiently.

Naively multiplying e times is O(e), which is far too slow for the exponents that show up in cryptography or “answer mod 10^9 + 7” problems. Fast exponentiation squares the base while halving the exponent.

def mod_pow(a, e, m):
    result = 1
    a %= m
    while e > 0:
        if e & 1:
            result = result * a % m
        a = a * a % m
        e >>= 1
    return result

Time is O(log e). Python’s built-in pow(a, e, m) does the same thing and is usually faster because it is implemented in C.

Modular inverses

Division is not directly defined in modular arithmetic. Instead, multiply by the modular inverse: a number a^{-1} such that a * a^{-1} ≡ 1 (mod m).

When m is prime, Fermat’s little theorem gives the inverse for free: a^{m-2} mod m.

def mod_inverse_prime(a, p):
    return pow(a, p - 2, p)

When m is not prime, use the extended Euclidean algorithm. If gcd(a, m) != 1, the inverse does not exist.

This unlocks computing binomial coefficients C(n, k) modulo a prime in constant time after O(n) preprocessing of factorials and inverse factorials, a staple of combinatorics problems.

Problem 1: Counting primes

Return the number of primes less than n.

The sieve answers this directly.

def count_primes(n):
    if n <= 2:
        return 0
    is_prime = bytearray([1]) * n
    is_prime[0] = is_prime[1] = 0
    for i in range(2, int(n ** 0.5) + 1):
        if is_prime[i]:
            is_prime[i * i : n : i] = bytearray(len(range(i * i, n, i)))
    return sum(is_prime)

The slice assignment trick zeroes a stride of the byte array in one C-level operation, which is dramatically faster than a Python loop.

Problem 2: Power of three

Determine whether n is a power of three.

The clever one-liner uses the fact that the largest power of three that fits in a 32-bit signed integer is 3^19 = 1162261467. Any positive divisor of that number is itself a power of three.

def is_power_of_three(n):
    return n > 0 and 1162261467 % n == 0

This is a fun reminder that “math” in interviews often means “find the clever invariant”, not “derive a formula”. A general approach uses repeated division:

def is_power_of_three_v2(n):
    if n < 1:
        return False
    while n % 3 == 0:
        n //= 3
    return n == 1

Problem 3: Fraction to recurring decimal

Given a numerator and denominator, return the decimal expansion as a string. Enclose the recurring part in parentheses.

This problem hides a beautiful number-theoretic fact: a fraction’s decimal expansion repeats once you revisit a remainder you have seen before. So track remainders in a hash map; when one recurs, you know where the cycle starts. The hash map pattern comes straight from Hashing and Hash Maps.

def fraction_to_decimal(num, den):
    if num == 0:
        return "0"
    sign = "-" if (num < 0) ^ (den < 0) else ""
    num, den = abs(num), abs(den)

    integer, remainder = divmod(num, den)
    result = [sign + str(integer)]
    if remainder == 0:
        return result[0]

    result.append(".")
    seen = {}
    while remainder and remainder not in seen:
        seen[remainder] = len(result)
        remainder *= 10
        digit, remainder = divmod(remainder, den)
        result.append(str(digit))

    if remainder:
        idx = seen[remainder]
        result.insert(idx, "(")
        result.append(")")
    return "".join(result)

Common identities worth memorizing

• a + b mod m = ((a mod m) + (b mod m)) mod m
• a * b mod m = ((a mod m) * (b mod m)) mod m
• gcd(a, b) * lcm(a, b) = a * b
• Sum of first n integers: n(n+1)/2
• Sum of first n squares: n(n+1)(2n+1)/6
• Number of divisors is multiplicative: if n = p1^a1 * p2^a2 * ..., then d(n) = (a1 + 1)(a2 + 1)...

Common pitfalls

• Negative modulo. In Python (-7) % 3 == 2, which is usually what you want, but in C, Java, and JavaScript it is -1. Normalize with ((x % m) + m) % m when porting.
• Overflow. Python integers are unbounded, so you can be sloppy. In other languages, multiply before taking mod and you will overflow.
• Inverse only when coprime. Always check gcd(a, m) == 1 before computing an inverse with extended Euclidean.
• Off-by-one in the sieve. range(2, int(n ** 0.5) + 1) is correct; forgetting the + 1 misses the largest prime factor of n.

Wrap up

You do not need a math degree to crush interview math problems. A solid grasp of the Euclidean algorithm, the sieve, fast modular exponentiation, and modular inverses covers the vast majority of what you will see. Combine these with the data-structure tools from Hashing and Hash Maps and the algorithmic patterns from Dynamic Programming Introduction, and the math-heavy questions stop feeling like a separate category.