GCD, prime numbers, modular arithmetic — the mathematical toolkit that shows up in places you wouldn't expect. From cryptography to competitive programming, these fundamentals keep coming back.
IntermediateNumber theory is the branch of mathematics that studies integers — whole numbers — and their properties. It's one of the oldest areas of math. The ancient Greeks were obsessed with it. Euclid wrote about prime numbers and the GCD algorithm around 300 BC, and we're still using his method in production code today. That's a 2,300-year-old algorithm running on your phone.
In the context of coding interviews and algorithm design, number theory boils down to four big topics: divisibility (GCD, LCM), prime numbers (finding them, testing them, factoring with them), modular arithmetic (clock math — where numbers wrap around), and combinatorics (counting arrangements and combinations).
You might wonder why a software engineer needs this stuff. Fair question. Here's the short answer: GCD shows up in fraction simplification, hash table sizing, and cryptography. Primes are the backbone of RSA encryption — every HTTPS connection you make relies on the difficulty of factoring large numbers. Modular arithmetic prevents integer overflow in competitive programming and powers rolling hash functions like Rabin-Karp. And combinatorics underpins probability, machine learning feature counting, and database query optimization.
The GCD (Greatest Common Divisor) of two integers is the largest number that divides both of them evenly. GCD(12, 8) = 4, because 4 is the biggest number that goes into both 12 and 8 without leaving a remainder. Another name for it: the highest common factor (HCF).
Think of it this way: if you have a 12×8 tile floor and want to cover it with the largest possible square tiles without cutting any, each tile would be 4×4. That's the GCD at work.
The Euclidean algorithm finds GCD efficiently. The idea: repeatedly replace the larger number with the remainder of dividing the two numbers. GCD(48, 18) → GCD(18, 12) → GCD(12, 6) → GCD(6, 0) → answer is 6. Each step shrinks the numbers fast — the algorithm runs in O(log(min(a,b))) time. Why so fast? Because the remainder is always less than half the larger number (you can prove this with a bit of algebra), so both numbers shrink by at least half every two steps.
The Least Common Multiple (LCM) of two numbers is the smallest positive integer that both numbers divide into evenly. LCM(4, 6) = 12. There's a neat relationship: LCM(a, b) × GCD(a, b) = a × b. So once you have GCD, LCM is a single multiplication and division away.
A prime number is an integer greater than 1 whose only divisors are 1 and itself. The sequence starts: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29... Notice that 2 is the only even prime — every other even number is divisible by 2. This is a common edge case in primality checks.
The Fundamental Theorem of Arithmetic says every integer greater than 1 can be written as a unique product of prime numbers (up to ordering). 60 = 2² × 3 × 5. 1001 = 7 × 11 × 13. This makes primes the "atoms" of number theory — every integer is built from them, and the decomposition is unique.
Testing if a single number n is prime: check if any integer from 2 to √n divides it evenly. Why √n? Because if n = a × b and both a and b are greater than √n, then a × b > n — contradiction. So at least one factor must be ≤ √n. This gives an O(√n) trial division algorithm.
Finding all primes up to n: use the Sieve of Eratosthenes (named after a Greek mathematician from ~240 BC). Start with a list of all numbers from 2 to n, all marked "potentially prime." Starting from 2, cross off all its multiples (4, 6, 8, ...). Move to the next unmarked number (3), cross off its multiples. Skip 4 (already crossed off). Continue to 5, and so on up to √n. Everything still unmarked is prime. The sieve runs in O(n log log n), which is nearly linear — incredibly fast for finding all primes up to n.
Modular arithmetic is arithmetic where numbers "wrap around" after reaching a certain value, called the modulus. A clock is the classic example: 14 o'clock is really 2 o'clock on a 12-hour clock. Mathematically, 14 mod 12 = 2. In code, the % operator does this (with some caveats for negative numbers — more on that in Common Mistakes).
The crucial property of modular arithmetic is that it distributes over addition and multiplication:
(a + b) % m = ((a % m) + (b % m)) % m(a × b) % m = ((a % m) × (b % m)) % mThis means you can take the mod at every step of a computation without changing the final result. Instead of computing some astronomically large number and then taking the mod, you keep numbers small throughout. This is essential when problems say "return the answer modulo 10⁹+7."
Why 10⁹+7 specifically? It's a prime number (1000000007), which means modular inverses exist for all non-zero values (needed for modular division). It's also small enough that two such numbers can be multiplied without overflowing a 64-bit integer.
Combinatorics is the math of counting things. Two building blocks show up constantly:
Pascal's Triangle gives you a fast way to compute combinations: C(n, r) = C(n-1, r-1) + C(n-1, r). Each entry is the sum of the two entries above it. This recurrence is the basis for DP solutions to many combinatorics problems.
Start with two numbers, a and b (assume a ≥ b). Divide a by b and take the remainder r. Now replace a with b, and b with r. Repeat until the remainder is 0. The last non-zero value is the GCD.
Concrete trace: GCD(252, 105):
Why does this work? The key insight: if d divides both a and b, then d also divides (a mod b), because a mod b = a − k·b for some integer k, and d divides both a and k·b. So the set of common divisors never changes through these substitutions — the GCD is preserved at every step.
Edge cases to know: GCD(0, n) = n. GCD(0, 0) is technically undefined, but most implementations return 0. Negative numbers: GCD is always non-negative, so take absolute values first.
The extended GCD does something extra: besides finding GCD(a, b), it also finds integers x and y such that ax + by = GCD(a, b). This equation is called Bézout's identity, and it always has integer solutions.
Why care? Because the extended GCD is how you compute modular inverses. The modular inverse of a (mod m) is a number x such that (a × x) mod m = 1. This only exists when GCD(a, m) = 1 (they're coprime — they share no common factors besides 1). The extended GCD gives you x directly.
Modular inverse is the tool for modular division. You can't just do (a / b) % m. Instead, you compute b's inverse and multiply: (a × b-1) % m.
Create a boolean array of size n+1, initially all true (meaning "assumed prime"). Mark indices 0 and 1 as false (they're not prime by definition).
The optimization of starting at i² (not 2i) matters. Any composite number less than i² with i as its smallest prime factor would have already been crossed off by a smaller prime. Starting at i² skips redundant work.
For n = 30, the sieve only needs to check primes up to √30 ≈ 5.47, so just 2, 3, and 5. After that, everything unmarked from 6 to 30 is prime.
Computing ab mod m directly would mean multiplying a by itself b times — O(b) operations on potentially huge numbers. Binary exponentiation (also called fast power or exponentiation by squaring) does it in O(log b) by exploiting the binary representation of the exponent.
The idea: write b in binary. For example, a13 where 13 = 1101₂ = 8 + 4 + 1. So a13 = a8 × a4 × a1. You compute a1, a2, a4, a8 by repeatedly squaring, and multiply together only the powers whose corresponding bit is set.
At each step, square the running base and take mod m. If the current bit of b is set, multiply the result by the base and take mod m. This keeps all intermediate values under m² — no overflow risk in 64-bit integers when m < 231.
For large n, computing C(n, r) = n! / (r!(n-r)!) directly overflows. Instead:
The inverse factorial is computed using Fermat's little theorem: if p is prime, then a-1 mod p = ap-2 mod p. So inv_fact[i] = pow(fact[i], p-2, p).
-7 % 3 = 2 (always non-negative). In C++, Java, and JavaScript, -7 % 3 = -1. This burns people constantly. If you need a non-negative result in C++/Java/JS, use ((a % m) + m) % m. Forgetting this is probably the #1 source of wrong answers in modular arithmetic problems.
LCM(a, b) = a / GCD(a, b) * b. Since GCD divides a evenly, the division is exact and you avoid the overflow. In Python this doesn't matter (arbitrary precision integers), but in C++/Java it's a trap.
(a / b) % m and expect the right answer. Modular division requires computing b's modular inverse: (a * mod_inverse(b, m)) % m. The inverse only exists when GCD(b, m) = 1. If m is prime (like 10⁹+7), every non-zero b has an inverse. If m isn't prime, you might be stuck.
| Algorithm | Time | Space | Notes |
|---|---|---|---|
| GCD (Euclidean) | O(log min(a,b)) | O(1) | Iterative version |
| Extended GCD | O(log min(a,b)) | O(log min(a,b)) | Recursive stack depth |
| Sieve of Eratosthenes | O(n log log n) | O(n) | Finds all primes ≤ n |
| Primality Test (trial div.) | O(√n) | O(1) | Single number check |
| Modular Exponentiation | O(log b) | O(1) | Computes a^b mod m |
| LCM via GCD | O(log min(a,b)) | O(1) | LCM = a/gcd * b |
| Prime Factorization | O(√n) | O(log n) | Number of prime factors |
| nCr mod p (precomputed) | O(1) per query | O(n) | After O(n log p) precomputation |
def gcd(a, b):
"""Iterative Euclidean algorithm.
Each step: replace (a, b) with (b, a % b).
Stops when remainder is 0 — the other number is the GCD.
Time: O(log(min(a, b))), Space: O(1)"""
while b:
a, b = b, a % b
return a
def lcm(a, b):
"""LCM(a,b) * GCD(a,b) = a * b.
Divide first to avoid integer overflow in typed languages."""
return a // gcd(a, b) * b
# Python 3.9+ has math.gcd and math.lcm built in.
# But knowing the implementation matters for interviews.
def extended_gcd(a, b):
"""Finds gcd(a,b) and coefficients x, y such that ax + by = gcd(a,b).
This is Bézout's identity. Used for modular inverse computation.
Returns (gcd, x, y)."""
if a == 0:
# Base case: 0*x + b*1 = b
return b, 0, 1
g, x1, y1 = extended_gcd(b % a, a)
# Back-substitute to find x and y for the current level
x = y1 - (b // a) * x1
y = x1
return g, x, y
def mod_inverse(a, m):
"""Modular inverse of a mod m using extended GCD.
Only exists when gcd(a, m) = 1 (a and m are coprime).
Returns x such that (a * x) % m == 1."""
g, x, _ = extended_gcd(a % m, m)
if g != 1:
raise ValueError(f"Inverse doesn't exist: gcd({a}, {m}) = {g}")
return x % m # ensure non-negative
function gcd(a, b) {
// Iterative Euclidean algorithm
while (b !== 0) {
[a, b] = [b, a % b];
}
return a;
}
function lcm(a, b) {
// Divide first to reduce overflow risk
return (a / gcd(a, b)) * b;
}
function extendedGcd(a, b) {
if (a === 0) return [b, 0, 1];
const [g, x1, y1] = extendedGcd(b % a, a);
return [g, y1 - Math.floor(b / a) * x1, x1];
}
def sieve(n):
"""Find all primes up to n using the Sieve of Eratosthenes.
Time: O(n log log n) — nearly linear.
Space: O(n) for the boolean array."""
is_prime = [True] * (n + 1)
is_prime[0] = is_prime[1] = False # 0 and 1 are not prime
# Only sieve up to sqrt(n).
# Any composite number <= n has a prime factor <= sqrt(n).
for i in range(2, int(n**0.5) + 1):
if is_prime[i]:
# Start crossing off at i*i, not 2*i.
# Smaller multiples (2i, 3i, ..., (i-1)*i) were already
# handled when we processed the smaller prime factor.
for j in range(i * i, n + 1, i):
is_prime[j] = False
return [i for i in range(n + 1) if is_prime[i]]
def sieve_smallest_factor(n):
"""Variant: compute the smallest prime factor for every number up to n.
Useful for fast factorization of many numbers."""
spf = list(range(n + 1)) # spf[i] = i initially
for i in range(2, int(n**0.5) + 1):
if spf[i] == i: # i is prime (no smaller factor found)
for j in range(i * i, n + 1, i):
if spf[j] == j: # only update if not already set
spf[j] = i
return spf
def prime_factors(n):
"""Find all prime factors of n with their multiplicities.
Trial division up to sqrt(n). Time: O(sqrt(n))."""
factors = {}
# Check factor 2 separately so we can skip evens after
while n % 2 == 0:
factors[2] = factors.get(2, 0) + 1
n //= 2
# Now n is odd. Check odd factors from 3 to sqrt(n).
d = 3
while d * d <= n:
while n % d == 0:
factors[d] = factors.get(d, 0) + 1
n //= d
d += 2
# If n > 1 here, it's a prime factor larger than sqrt(original_n)
if n > 1:
factors[n] = 1
return factors
# Example: prime_factors(360) = {2: 3, 3: 2, 5: 1}
# Because 360 = 2^3 * 3^2 * 5
def mod_pow(base, exp, mod):
"""Binary exponentiation: compute base^exp % mod in O(log exp).
Works by decomposing exp into powers of 2.
Example: 3^13 = 3^8 * 3^4 * 3^1 (13 = 1101 in binary)."""
result = 1
base %= mod # handle base >= mod
while exp > 0:
if exp & 1: # if current bit is set
result = result * base % mod # multiply into result
exp >>= 1 # shift to next bit
base = base * base % mod # square the base
return result
# Python has this built in: pow(base, exp, mod)
# Use the built-in in production — it handles edge cases.
# Fermat's little theorem shortcut for modular inverse:
# If p is prime and gcd(a, p) = 1, then a^(-1) mod p = a^(p-2) mod p
def mod_inverse_fermat(a, p):
"""Only works when p is prime."""
return pow(a, p - 2, p)
function modPow(base, exp, mod) {
// Use BigInt to avoid precision loss with large numbers
let result = 1n;
base = BigInt(base) % BigInt(mod);
exp = BigInt(exp);
const m = BigInt(mod);
while (exp > 0n) {
if (exp & 1n) result = result * base % m;
exp >>= 1n;
base = base * base % m;
}
return Number(result);
}
MOD = 10**9 + 7
def precompute_factorials(n):
"""Precompute factorials and inverse factorials mod MOD.
After this, nCr queries are O(1) each."""
fact = [1] * (n + 1)
for i in range(1, n + 1):
fact[i] = fact[i - 1] * i % MOD
# Compute inverse factorials using Fermat's little theorem
inv_fact = [1] * (n + 1)
inv_fact[n] = pow(fact[n], MOD - 2, MOD)
# Work backwards: inv_fact[i] = inv_fact[i+1] * (i+1)
for i in range(n - 1, -1, -1):
inv_fact[i] = inv_fact[i + 1] * (i + 1) % MOD
return fact, inv_fact
def nCr(n, r, fact, inv_fact):
"""O(1) combination query after precomputation."""
if r < 0 or r > n:
return 0
return fact[n] * inv_fact[r] % MOD * inv_fact[n - r] % MOD
# Usage:
# fact, inv_fact = precompute_factorials(100000)
# print(nCr(10, 3, fact, inv_fact)) # 120
Here's a concrete use of GCD and LCM in production code. Imagine you're building a rate limiter that allows different API tiers: free users get 60 requests per minute, premium users get 200 per minute, and enterprise gets 1000 per minute. You want a single timer that can tick at a rate compatible with all tiers.
from math import gcd
from functools import reduce
def find_tick_interval(rates):
"""Find the optimal tick interval (in ms) for a rate limiter
that supports multiple rate tiers.
Each rate is "requests per minute." We need a tick interval
that divides evenly into all rate periods.
The answer is 60000ms / LCM(all rates), giving us the
finest granularity that works for every tier."""
def lcm(a, b):
return a // gcd(a, b) * b
combined_lcm = reduce(lcm, rates)
tick_ms = 60000 // combined_lcm # ms per tick
print(f"Rates: {rates}")
print(f"LCM: {combined_lcm}")
print(f"Tick interval: {tick_ms}ms")
print(f"Tokens per tick per tier:")
for rate in rates:
tokens = combined_lcm // rate
print(f" {rate} req/min → {tokens} token(s) every {tick_ms}ms")
return tick_ms
# Real example: 3 API tiers
find_tick_interval([60, 200, 1000])
# LCM(60, 200, 1000) = 1000
# Tick every 60ms
# 60 req/min tier: ~16 tokens per tick
# 200 req/min tier: 5 tokens per tick
# 1000 req/min tier: 1 token per tick
Another common production use: fraction display. If your app shows "3/4 complete" instead of "0.75 complete," you need to simplify fractions. That's GCD.
def simplify_fraction(numerator, denominator):
"""Reduce a fraction to lowest terms using GCD.
Used in progress displays, recipe scaling, and unit conversion."""
if denominator == 0:
raise ValueError("Denominator cannot be zero")
# Handle negative fractions: put the sign on the numerator
sign = -1 if (numerator < 0) ^ (denominator < 0) else 1
n, d = abs(numerator), abs(denominator)
g = gcd(n, d)
return sign * (n // g), d // g
# simplify_fraction(150, 200) → (3, 4)
# simplify_fraction(-6, 9) → (-2, 3)
(a * b) % m = ((a % m) * (b % m)) % m. The mod value 10⁹+7 was chosen because it's prime (enabling modular inverses) and fits in a 32-bit integer.
| # | Problem | Difficulty | Key Concept |
|---|---|---|---|
| 204 | Count Primes | Medium | Sieve of Eratosthenes |
| 1071 | GCD of Strings | Easy | Euclidean GCD on strings |
| 50 | Pow(x, n) | Medium | Fast exponentiation |
| 372 | Super Pow | Medium | Modular exponentiation |
| 2183 | Count Array Pairs Divisible by K | Hard | GCD + factor enumeration |
| 878 | Nth Magical Number | Hard | LCM + binary search |
| 1175 | Prime Arrangements | Easy | Counting primes + factorials |
| 2654 | Min Ops to Make All Equal to 1 | Medium | Subarray GCD |
| 62 | Unique Paths | Medium | Combinatorics (nCr) |