skip to content

You must choose two moduli for a two-coordinate placement scheme over a fixed identifier range - what decides the pair?

level: principalimportance: should knowfreq 32%

answer

  1. the pair of moduli fixes the ceiling
  2. shared factor shrinks the usable space
  3. reachable count is the least common multiple
  4. range above capacity forces collisions
  5. resizing remaps nearly every identifier

basics

~20 s

Coprimality and size decide it: coprime moduli make the two coordinates independent and reach all of their product, while the product must cover the identifier range or collisions are forced. A shared factor shrinks the reachable space to the least common multiple.

solid answer

~40 s

Two constraints are arithmetic, not negotiable. First, **coprimality**: only then does every combination of the two coordinates occur, and only then is a value recoverable from the pair. Second, **capacity**: the reachable address count is `lcm(m, n)`, which equals `m*n` under coprimality, and if the identifier range exceeds it then some identifiers must collide - that is pigeonhole, not an implementation flaw. Beyond those, the judgment is about the shape of the moduli you actually want: coordinate sizes that match what each dimension physically means, a realignment period of `m*n` that is long enough to matter, and the awareness that changing either modulus later remaps every identifier, since the arithmetic offers no continuity under a resize.

go deeper

for a junior

Know the first check: the two moduli should share no factor above 1, or the two coordinates partly duplicate each other and fewer addresses exist than the product suggests.

for a middle

Compute the real capacity as the least common multiple, and show why (8, 12) loses to (8, 9) despite the larger product. Then check the capacity against the identifier range.

for a senior

Argue the collision case from counting rather than from testing, and be explicit that exceeding capacity is forced, not a defect - so the system needs a defined behaviour for it.

for a principal

Own the one-way door: the moduli fix capacity and realignment period, and changing either remaps everything. Size against the range you expect to reach, and say so in writing before anything is built on the addressing.

## What the moduli are really deciding A two-coordinate placement scheme maps an identifier `x` to the pair `(x mod m, x mod n)`. Three properties of the scheme follow from `m` and `n` alone, before any code exists: - **how many distinct addresses exist** - `lcm(m, n)`, which is `m*n` exactly when `gcd(m, n) = 1`; - **whether the pair can be inverted** back to the identifier - it can, uniquely modulo `lcm(m, n)`; - **how long before the combination repeats** - again `lcm(m, n)` steps. That is the entire mathematical content of the decision, and it is why this is a design question rather than an implementation one: the arithmetic decides the ceiling, and no amount of engineering raises it. ## The two hard constraints 1. **Coprimality.** With `gcd(m, n) = g > 1`, the two remainders both reduce to the same residue modulo `g`, so they are partly redundant: `g` of every `g` combinations is unreachable, and each reachable one is shared by `g` identifiers per `lcm` window. A pair like `(8, 12)` offers 96 apparent cells and 24 real ones. A pair like `(8, 9)` offers 72 and uses all 72. 2. **Capacity.** If the identifier range exceeds `lcm(m, n)`, two identifiers share an address. This is forced by counting and cannot be engineered away; the only responses are a larger product, or accepting and handling the collision explicitly. | pair | product | reachable addresses | realignment period | |---|---|---|---| | (8, 9) | 72 | 72 | 72 | | (5, 7) | 35 | 35 | 35 | | (6, 10) | 60 | 30 | 30 | | (8, 12) | 96 | 24 | 24 | The last row is the trap: it has the largest product of the four and the smallest usable space. ## The judgment calls the arithmetic does not make - **What each coordinate means.** One modulus is usually constrained by something real - a count of destinations you can actually operate - so the free choice is typically the second, and the job is to pick it coprime to the first and large enough that the product clears the identifier range. - **How far above the range to aim.** Exactly meeting the range leaves no headroom; a much larger product buys headroom at the price of coordinates larger than either dimension needs. - **Prime or prime-power moduli.** Choosing primes makes coprimality automatic and keeps it automatic if a third coordinate is added later - but the requirement there is **pairwise** coprimality, and three moduli with no single common factor can still fail every pair. - **Whether both coordinates are worth keeping.** If a shared factor is forced by outside constraints, the pair is carrying less information than its size implies, and one coordinate modulo `lcm(m, n)` carries the same information more honestly. ## The property the mathematics will not give you There is no continuity under a resize. Changing either modulus changes `x mod m` for almost every `x`, so every identifier moves. The scheme is cheap to compute and effectively irreversible to adjust, which means the sizing decision is a one-way door and should be made against the identifier range you expect to reach, not the one you have. If resizing without wholesale remapping is a requirement, this family of schemes is the wrong tool and the requirement should be surfaced before the moduli are chosen, not after. ## A defensible way to reach the answer 1. Fix the identifier range you must address, as a number. 2. Fix whichever modulus is externally constrained. 3. Choose the second modulus coprime to the first, with the product comfortably above step 1's number. 4. Verify by counting: `gcd = 1`, reachable addresses `= m*n`, and `m*n` at or above the range. 5. Write down, explicitly, what happens when the range is exceeded - because it eventually will be, and pigeonhole guarantees the collision. ## What a weak answer looks like It picks two round numbers, multiplies them, and reports the product as the capacity. Both parts of that are wrong when the moduli share a factor: the capacity is the least common multiple, and the missing cells are not a rounding error but three quarters of the space in the `(8, 12)` case. The check that catches it is one line of arithmetic, and it belongs in the design note rather than in a later incident.

  • Two candidate pairs are (8, 12) and (8, 9). Which gives more addresses, and by how much?
    (8, 9), by three times. Its moduli are coprime, so all `72` combinations occur. (8, 12) has the larger product, 96, but `gcd = 4`, so only `lcm(8, 12) = 24` addresses are reachable and each is shared by four identifiers. The larger product is the misleading number.
  • The identifier range is larger than the product of the two moduli. What follows?
    Collisions are unavoidable. More identifiers than addresses means at least two share a pair, by pigeonhole, regardless of how the reconstruction is implemented. The choice is to enlarge a modulus so the product clears the range, or to define explicitly what a shared address means for the system.
  • Does choosing three prime moduli automatically make the scheme sound?
    Distinct primes are pairwise coprime, so yes for that clause - but repeating a prime breaks it, since a modulus is not coprime to itself. And coprimality is only half the requirement: the product of all three must still cover the identifier range, or the scheme collides regardless.

saying these in an interview costs you the question

  • Quotes the product as capacity without checking the gcd
  • Picks two round, even moduli and assumes independent coordinates
  • Believes collisions past the capacity are an implementation bug
  • Assumes a modulus can be resized later without remapping identifiers
  • Checks three moduli for a single shared factor instead of pairwise