228: Mathematics for DSA: GCD, Primes, Modular Arithmetic, Combinatorics, and Overflow

Learning outcomes

By the end of this lesson, you can:

explain and apply euclidean gcd in a realistic implementation;
explain and apply prime testing and sieve in a realistic implementation;
explain and apply modular arithmetic in a realistic implementation;
explain and apply fast exponentiation in a realistic implementation;
explain and apply combinatorics in a realistic implementation.

These outcomes are deliberately implementation-oriented. Knowing the name of an algorithm is not enough: you should be able to connect it to an input contract, state the invariant that makes it correct, account for numeric limits, and explain how you would test it.

Prerequisites and retrieval

This lesson assumes the earlier 01–06 foundation and the preceding lessons in this module. Before reading, retrieve one concrete example from a previous project where the same concern appeared. Perhaps you reduced a ratio, needed to count possibilities, generated candidate values, or discovered that an apparently ordinary arithmetic operation exceeded the representation's safe range. The point is to connect the mathematics to a real engineering decision rather than memorize terminology in isolation.

The target is an interview-sized problem and a production data-processing problem. In both settings, reason from constraints: input size, allowed output range, precision requirements, and failure behavior. A formula that is mathematically correct can still be the wrong implementation if its intermediate values overflow or if its runtime is too high for the actual workload.

Terminology

Euclidean GCD: Repeatedly replace (a,b) with (b,a mod b) until b = 0; the nonzero value left in a is the greatest common divisor. The transformation preserves the gcd, which is the reason the process is safe.
Prime testing and sieve: Trial division up to sqrt(n) tests one number; the Sieve of Eratosthenes marks composites to generate primes up to N in near-linearithmic time. The choice depends on whether you have one candidate or a range of candidates.
Modular arithmetic: Addition and multiplication can be reduced modulo m; subtraction needs normalization so the result is represented in the expected range. Division requires a multiplicative inverse and is not ordinary integer division.
Fast exponentiation: Exponentiation by squaring computes a^n in O(log n) multiplications and combines naturally with a modulus to keep intermediate values bounded.
Combinatorics: Permutations, combinations, binomial coefficients, and inclusion/exclusion often count possibilities without enumerating them. Dynamic programming or Pascal tables can avoid huge factorial intermediates in some contexts.
Numeric range: JavaScript Number is exact only for integers through Number.MAX_SAFE_INTEGER. Use BigInt or modular arithmetic when counts or products exceed the safe integer range, and do not mix Number and BigInt in arithmetic without an explicit conversion.

Mental model

Treat Mathematics for DSA: GCD, Primes, Modular Arithmetic, Combinatorics, and Overflow as a design problem with observable inputs, outputs, invariants, and failure modes. Number theory is useful because it gives you properties that remain true while the algorithm transforms the data. Those properties simplify fraction reduction, divisibility checks, prime generation, counting, and exponentiation. They do not remove the need to check representation limits or define behavior at boundaries.

A strong implementation makes assumptions visible. It narrows uncertainty at the input boundary, states what must remain true after each iteration, and leaves enough evidence—tests, types, constraints, metrics, or diagrams—to show why the design is safe. When an answer is wrong, the invariant also gives you a place to start debugging: find the first step at which it stops being true.

A useful interview and production sequence is:

requirement -> constraints -> model -> implementation -> failure analysis -> verification

Do not jump from a requirement directly to a library call or a remembered code template. First state what must remain true. Then choose the mechanism that enforces it. For example, “return a remainder” is incomplete unless you know whether the contract expects a nonnegative representative, what values m may take, and whether exact integer arithmetic is available.

Deep dive

1. Euclidean GCD

When two numbers share factors, testing every possible divisor is unnecessary. The Euclidean algorithm repeatedly replaces (a,b) with (b,a mod b) until b = 0. The gcd does not change during that replacement because the common divisors of a and b are exactly the common divisors of b and a mod b. Once the remainder is zero, a is the greatest common divisor.

GCD supports fraction reduction, LCM, cyclic structure, and divisibility reasoning. The iterative form uses O(log min(a,b)) remainder steps for nonnegative inputs and O(1) auxiliary space. A production implementation should make its policy for zero, negative values, and non-integers explicit rather than relying on coercion. For example, gcd(a, 0) is |a| under the usual integer definition, while gcd(0, 0) needs a documented convention because there is no unique greatest positive divisor.

Decision rule: Use euclidean gcd deliberately when it makes the contract or invariant easier to prove. If it only reduces typing while hiding an assumption, prefer the more explicit design. This is especially relevant when the surrounding code accepts untrusted or loosely typed values: validate first, then run the integer algorithm.

2. Prime testing and sieve

For one candidate number, trial division is usually enough. You only need to test divisors through sqrt(n): if n has a factor larger than its square root, its paired factor is smaller than the square root and would already have been found. After handling values below 2, checking only possible divisors can test one number in O(sqrt(n)) time.

When you need every prime up to N, repeating trial division wastes work. The Sieve of Eratosthenes creates a boolean table, starts with the smallest unmarked candidate, and marks its multiples as composite. Marking can begin at p * p, because smaller multiples have already been handled by smaller prime factors. The sieve takes O(N log log N) time and O(N) space, commonly described as near-linearithmic. A range query, memory budget, or very large N may require a segmented or otherwise specialized sieve instead.

Decision rule: Use prime testing and sieve deliberately when it makes the contract or invariant easier to prove. If it only reduces typing while hiding an assumption, prefer the more explicit design. The key question is whether you are answering one candidate query or amortizing work across a bounded range.

3. Modular arithmetic

Modular arithmetic is useful when exact values become enormous but only their remainder modulo m matters. Addition and multiplication can be reduced modulo m during the calculation because (a + b) mod m and (a * b) mod m depend only on the operands' residues. That keeps values bounded, although the multiplication itself must still be safe in the chosen numeric representation.

Subtraction is where people usually get confused. In JavaScript, % is a remainder operator and can produce a negative result, so normalize when the contract expects a value in [0, m): ((a - b) % m + m) % m. Division is different. You may divide by b modulo m only when a multiplicative inverse of b exists under the modulus; ordinary integer division is not a valid substitute. The modulus must also be validated, normally as a positive integer.

Decision rule: Use modular arithmetic deliberately when it makes the contract or invariant easier to prove. If it only reduces typing while hiding an assumption, prefer the more explicit design. State whether the result is a mathematical congruence, a normalized residue, or a value that must be represented exactly.

4. Fast exponentiation

Multiplying a by itself n times takes O(n) multiplications. Exponentiation by squaring uses the binary representation of n instead: square the base at each step, and multiply it into the result only when the current exponent bit is set. This reduces the work to O(log n) multiplications and uses O(1) auxiliary space in an iterative implementation.

The same structure works for modular powers. Reduce the result and base after each multiplication so the values remain bounded by the modulus. This is valuable for large exponents, but it does not magically make an unsafe Number multiplication safe: either the modulus and operands must fit the representation, or the implementation must use BigInt and consistently typed operands.

Decision rule: Use fast exponentiation deliberately when it makes the contract or invariant easier to prove. If it only reduces typing while hiding an assumption, prefer the more explicit design. Define the behavior for exponent zero, negative exponents, and invalid inputs before selecting the loop.

5. Combinatorics

Many counting problems look as if they require enumerating every possibility. Often the structure lets you count directly. Permutations count ordered selections, combinations count unordered selections, binomial coefficients count the ways to choose k items from n, and inclusion/exclusion corrects for overlap between sets. The distinction between ordered and unordered choices is the first place to slow down; using the wrong one produces a plausible but incorrect answer.

The familiar formula C(n,k) = n! / (k!(n-k)!) is mathematically clear, but calculating three factorials can create huge intermediate values even when the final answer is manageable. A multiplicative formulation, a Pascal-table dynamic program, or modular factorials and inverses can be safer depending on the constraints. Pascal's triangle uses O(nk) time and O(k) space when only one row is retained; direct factorial-based approaches need a precise numeric-range strategy.

Decision rule: Use combinatorics deliberately when it makes the contract or invariant easier to prove. If it only reduces typing while hiding an assumption, prefer the more explicit design. Confirm whether the result needs to be exact, reduced modulo a prime, or merely compared with a threshold before choosing a representation.

6. Numeric range

JavaScript Number is exact only for integers through Number.MAX_SAFE_INTEGER. Above that boundary, two different mathematical integers can map to the same floating-point value, so equality, counting, and multiplication can silently become wrong rather than throwing an error. This is a correctness issue, not just a formatting issue.

Use BigInt when exact integer values are required beyond the safe range, or use modular arithmetic when the problem asks only for a remainder. BigInt has its own contract: literals use an n suffix, arithmetic operands must be consistently BigInt, and conversion back to Number is safe only when you have checked the range. BigInt operations also have different performance and serialization characteristics, so select it intentionally.

Decision rule: Use numeric range deliberately when it makes the contract or invariant easier to prove. If it only reduces typing while hiding an assumption, prefer the more explicit design. Write down the largest possible input, intermediate result, and output before deciding that ordinary Number arithmetic is acceptable.

Worked example

Consider an interview-sized problem and a production data-processing problem, so the learner must reason from constraints rather than memorize a template. Start by writing the requirement in one sentence, list the input and output contracts, and identify which of the concepts above owns each failure mode. The important move is separation: parsing or validation belongs at the boundary; domain rules belong in the domain/service layer; persistence rules belong in the database or repository; presentation rules belong in the client. Mixing these concerns makes a happy-path demo look shorter but makes edge cases much harder to reason about.

The following small function is intentionally simple. It finds the largest value, and its loop invariant is that answer is the maximum of every value visited so far. It is not an implementation of the number-theory algorithms above; it is a reminder to state the invariant before selecting the data structure or loop shape.

function solve(values: readonly number[]): number {
  let answer = 0;
  // State the invariant before choosing the data structure.
  for (const value of values) {
    answer = Math.max(answer, value);
  }
  return answer;
}

That code also exposes a contract question: initializing answer to 0 is wrong if negative values are valid, and an empty input needs a defined result or an error. The same habit applies to gcd, sieves, modular calculations, and combinations. Identify the valid domain first; then make the implementation preserve the promised property for every value in that domain.

Walk the example with at least four cases: the normal path, an empty or missing value, a duplicate/retry/concurrent path where relevant, and a dependency failure. For each case, state which layer detects the problem and what the caller observes. This is the level of explanation expected in a senior code review or technical interview. For the mathematical functions, add cases for zero, values below the natural domain, the smallest valid inputs, repeated values, and values near the numeric boundary.

Production perspective

Production correctness is broader than “the code works on my machine.” Ask how the design behaves during deploys, retries, partial failure, stale clients, concurrent requests, malformed data, schema changes, and high cardinality. For mathematical utilities, also ask whether a caller can pass a negative value, a non-integer, an invalid modulus, or a value that causes an intermediate result to exceed the safe range. Prefer explicit contracts, bounded resource usage, structured errors, and measurable behavior. Optimize only after you can identify the bottleneck or risk with evidence.

When the topic involves an external dependency, define a timeout and cancellation strategy. When it involves persistence, define transaction and consistency expectations. When it involves user-visible state, define loading, empty, error, stale, and success states. When it involves security, assume the client can be modified and the network input is untrusted. A mathematical helper may be locally pure, but the service that accepts its inputs still has boundary-validation and abuse-resistance responsibilities.

Guided lab

Implement gcd/lcm, prime sieve, modular exponentiation, and n-choose-k using a safe approach. Add tests near Number safe-integer boundaries and repeat one calculation with BigInt. For each function, document valid inputs and the expected result for the smallest meaningful cases. In particular, decide how the implementation handles zero in gcd/lcm, values below 2 in prime logic, modulus validation, exponent zero, and k outside [0,n].

Complete the lab with this discipline:

Write the requirement and two non-requirements.
List input, output, and error contracts before implementation.
Implement the smallest correct vertical slice.
Add at least one invalid-input test and one edge-case test.
Instrument or inspect the behavior instead of guessing.
Refactor one hidden assumption into an explicit type, constraint, function, or configuration.
Explain one alternative design and why you did not choose it.
Record a short “what would break at 10× scale?” note.

For the scale note, consider more than elapsed time. A sieve may exhaust memory, factorial intermediates may lose precision, and BigInt or modular arithmetic may change the API and serialization behavior. The exercise is complete when you can explain both why the chosen implementation is correct and where its limits are.

Edge cases and failure modes

Euclidean GCD: test absence, malformed input, duplicates, ordering/concurrency where applicable, and behavior at the smallest and largest credible sizes. Also define zero, negative values, non-integers, and the gcd(0, 0) policy.
Prime testing and sieve: test absence, malformed input, duplicates, ordering/concurrency where applicable, and behavior at the smallest and largest credible sizes. Include values below 2, 0, 1, perfect squares, and a sieve limit of 0 or 1.
Modular arithmetic: test absence, malformed input, duplicates, ordering/concurrency where applicable, and behavior at the smallest and largest credible sizes. Check negative subtraction, invalid or nonpositive moduli, and whether multiplication remains safe for the selected representation.
Fast exponentiation: test absence, malformed input, duplicates, ordering/concurrency where applicable, and behavior at the smallest and largest credible sizes. Include exponent 0, base 0, negative exponents if they are rejected or supported, and overflow or modulus behavior.
Combinatorics: test absence, malformed input, duplicates, ordering/concurrency where applicable, and behavior at the smallest and largest credible sizes. Include k = 0, k = n, k > n, negative inputs, symmetry checks such as C(n,k) = C(n,n-k), and large intermediate values.

The generic cases in each row are a prompt to inspect the surrounding API as well as the formula. “Ordering/concurrency where applicable” may not apply to a pure function, but it matters when these calculations are used in a shared cache, batch job, request handler, or retried data pipeline.

Common mistakes and debugging

Solving the example instead of the requirement: a copied pattern can be syntactically correct but architecturally wrong.
Hiding uncertainty with assertions, broad exception handlers, permissive schemas, or “temporary” any values.
Testing only the happy path and therefore discovering contracts only after integration.
Optimizing before measuring, or selecting a scalable mechanism without a scale requirement.
Letting client-side behavior stand in for server-side authorization, validation, or persistence guarantees.
Assuming % always returns a nonnegative mathematical modulo, or assuming factorial formulas are safe simply because the final answer fits.
Mixing Number and BigInt, or converting a large exact integer back to Number without checking its range.

For debugging, reproduce the smallest failing case, inspect the actual value or execution plan, trace the boundary where the invariant first becomes false, and fix the owning layer rather than adding a downstream patch. If a modular result is negative, inspect normalization and the modulus contract. If a prime result is slow, inspect whether one candidate is being tested repeatedly instead of using a sieve. If a count is inconsistent near a boundary, log the representation and intermediate values before changing the formula.

Interview questions

What problem does Euclidean GCD solve, and what trade-off or failure mode would make you choose a different approach?
What problem does Prime testing and sieve solve, and what trade-off or failure mode would make you choose a different approach?
What problem does Modular arithmetic solve, and what trade-off or failure mode would make you choose a different approach?
What problem does Fast exponentiation solve, and what trade-off or failure mode would make you choose a different approach?
What problem does Combinatorics solve, and what trade-off or failure mode would make you choose a different approach?

Answer these with more than a definition. State the input shape, the invariant or complexity argument, the relevant boundary case, and the reason an alternative might be preferable. For example, a sieve is a good answer for many candidates in a bounded range, but not automatically for a single enormous candidate or an input range that cannot fit in memory.

Checkpoint

Without notes, explain Mathematics for DSA: GCD, Primes, Modular Arithmetic, Combinatorics, and Overflow to another developer in five minutes. Your explanation must include one invariant, one edge case, one production failure mode, and one alternative design. Then implement a small example without copying the lesson code.

As a self-check, make sure the explanation covers both the mathematical idea and the JavaScript representation decision. A correct formula implemented with unsafe Number operations is not a correct solution. The listener should be able to tell what you would validate, how you would measure complexity, and what evidence would help you debug a failing result.

Mastery checklist

I can define the core terms precisely.
I can choose a design from requirements instead of from habit.
I can implement and test the normal path and edge cases.
I can explain the runtime, storage, or complexity cost.
I can identify which layer owns validation, errors, and recovery.
I can compare at least two reasonable alternatives.
I can explain how the design changes at larger scale or stricter reliability.