Math & Number Theory

01 / The shared mechanism

Many problems hide a number-theoretic backbone. Once you recognize the divisibility / modular / multiplicative structure the input really has, an O(N) loop collapses to O(log N) or O(N log log N). Three classic sub-patterns: gcd by Euclidean reduction, modular power by exponent-bit doubling, prime sieve by marking multiples once.

01 / The one-sentence essence

gcd(a, b) = gcd(b, a % b) — the divisor that divides both also divides the remainder, so we can keep swapping in the smaller residue without losing the answer. Each step the pair shrinks geometrically; log(min(a, b)) iterations and we're done. LCM rides on top: a / gcd(a, b) · b.

Problemgcd(a, b) and lcm(a, b)a24b36

Start with a = 24, b = 36. Apply gcd(a, b) = gcd(b, a % b) until b = 0.

step

0 / 5

gcd

—

lcm

—

0 / 5

a, b

02 / The pattern signature

# Euclidean gcd — terminate when the right pair-element is 0def gcd(a, b):while b ≠ 0:a, b ← b, a % b # shrinkreturn a# LCM — divide first to avoid overflowdef lcm(a, b):return a / gcd(a, b) · b

03 / When to recognize this pattern

"greatest common divisor / common factor"

The canonical use. LC 1071 — "largest string that divides both" reduces to taking the GCD of the two string lengths. Whenever the problem speaks of a common factor, common divisor, or "largest unit that fits both", Euclid is the answer.

"least common multiple / period"

Use whenever you need the smallest number that both a and b divide — synchronized cycles, repeating signals, "earliest time both events line up". Compute gcd first, then a / gcd · b — the divide-first form stays within 64-bit even when a · b would overflow.

"is fraction in lowest terms / coprime"

Two numbers are coprime iff gcd(a, b) = 1. Reducing p/q to lowest terms is one GCD call and two divisions. Hash invariants for rational keys, Stern–Brocot tree navigation, Farey neighbours — all hinge on this.

"GCD of an entire array"

LC 1979. The gcd of {a₁, …, aₙ} is gcd(…gcd(gcd(a₁, a₂), a₃)…, aₙ) — fold pairwise. The intermediate value can only shrink (or stay the same), and once it hits 1 you can early-exit; the total work is still bounded by the sum of the individual reductions.

04 / Common pitfalls

Computing LCM as a · b / gcd(a, b) without dividing first.

Multiplying first can overflow on 32-bit ints — and on 64-bit too if a and b approach 2³¹. Always divide first: a / gcd(a, b) · b. The division is exact (gcd divides a), so the order is safe and the intermediate value never exceeds the final answer.

ii.

Forgetting the b == 0 termination.

Without the guard you either loop forever (a % 0 is undefined or raises) or — worse — get a divide-by-zero crash on the very first step when b == 0. gcd(a, 0) = a by definition; let that case fall out of the loop cleanly.

iii.

Sign of the result with negative inputs.

By convention gcd is non-negative; some language built-ins (e.g. C's %) return signs that depend on dividend, so an unguarded recursion can land on a negative a. Take abs(a) and abs(b) at the entry, or use the language's math-style modulo. Python's % follows the divisor's sign and works as-is; C/Java do not.

05 / Go practice — on LeetCode

Four problems. The first three are direct applications of the Euclidean reduction; the last uses Bézout's identity — that gcd(a, b) is the smallest positive integer expressible as a·x + b·y — to decide feasibility.

01Greatest Common Divisor of Strings— LC 1071easy→02Find Greatest Common Divisor of Array— LC 1979easy→03X of a Kind in a Deck of Cards— LC 914easy→04Water and Jug Problem— LC 365medium→

— / When to use which

gcd / lcm

Use whenever divisibility is the heart of the problem — common factor, coprimality test, simplest fraction, LCM via a · b / gcd(a, b). Euclid's identity gcd(a, b) = gcd(b, a % b) drops each step geometrically.

Euclidean · LC 1071 · LC 1979

modular power

Use whenever you need aⁿ mod M for huge n, or a multiplicative inverse mod a prime. Halve the exponent each step; the bit pattern of n picks which squarings contribute. O(log n) instead of O(n).

exponent halving · LC 50 · LC 372

prime sieve

Use when you need all primes up to N (or all smallest prime factors). For each prime p walk its multiples and mark them composite — every composite is marked O(log log N) times amortized.

Eratosthenes · LC 204 · LC 952