skip to content

Two placement coordinates use the moduli 8 and 12 - what does sharing the factor 4 cost that scheme?

level: seniorimportance: nice to knowfreq 28%

answer

  1. the two coordinates are not independent
  2. both reduce the same way modulo the gcd
  3. some remainder pairs never occur
  4. solvable only when remainders agree mod gcd
  5. uniqueness runs to the lcm, not the product

basics

~20 s

Only 24 of the 96 remainder pairs ever occur, because both coordinates must agree modulo the gcd 4, and each pair that does occur is shared by four values below 96. Addressing is unique only modulo the lcm 24, not the product.

solid answer

~40 s

With `gcd(8, 12) = 4`, a value's two remainders are not independent: both reduce to the same residue modulo 4. So a pair like `(1 mod 8, 2 mod 12)` is **unsolvable** - 1 and 2 disagree modulo 4 - and only `24` of the `96` grid cells are reachable. Worse, reachable is not unique: `x` congruent to 1 modulo 8 and 5 modulo 12 is satisfied by 17, 41, 65 and 89, four values below 96, because uniqueness runs only to `lcm(8, 12) = 24`. The general rule is that the system is solvable exactly when the remainders agree modulo the gcd, and then the solution is unique modulo the lcm - which equals the product only when the moduli are coprime.

go deeper

for a junior

The takeaway to hold: two remainders only act as independent coordinates when the two moduli share no factor. With 8 and 12 they are partly telling you the same thing.

for a middle

Explain the constraint: both remainders must agree modulo the gcd, which kills most pairs outright, and the surviving ones repeat every lcm rather than every product.

for a senior

Count it. 96 cells, 24 reachable, 4 values each, uniqueness window 24 - and be precise that the harm is dead cells plus collisions, not uneven load.

for a principal

The judgment is whether to change a modulus, resize against the lcm, or admit the second coordinate is partly redundant and collapse it. Each is defensible; picking silently is not.

## The general statement, with the coprime case as a special case For arbitrary moduli `m` and `n`, the system "`x` congruent to `a` modulo `m`, `x` congruent to `b` modulo `n`" behaves like this: - it has a solution **exactly when** `a` and `b` are congruent modulo `g = gcd(m, n)`; - when it has one, the solution is unique **modulo `lcm(m, n)`**. The familiar Chinese remainder theorem is the case `g = 1`, where the solvability condition is vacuous (everything is congruent modulo 1) and `lcm(m, n) = m*n`. Coprimality is not a tidiness requirement; it is what makes both clauses collapse into "always solvable, unique modulo the product". ## The 8-and-12 grid, counted Take `m = 8` and `n = 12`, so `g = 4`, `lcm = 24`, and the product is `96`. Any `x` reduces modulo 4 in one way only, and both coordinates inherit it: `a mod 4` and `b mod 4` are the same number. That single constraint decides the whole picture. | quantity | value | why | |---|---|---| | grid cells `(a, b)` | 96 | 8 choices times 12 choices | | reachable cells | 24 | for each `a`, only the 3 values of `b` agreeing modulo 4 | | values per reachable cell | 4 | 96 values spread over 24 cells | | uniqueness window | 24 | `lcm(8, 12)` | So three quarters of the address space is permanently empty, and the quarter that is used is four-way ambiguous. ## The two failures are different, and both matter 1. **Unsolvable pairs.** Asking for `x` congruent to 1 modulo 8 and 2 modulo 12 has no answer at all: `1 mod 4 = 1` while `2 mod 4 = 2`. A scheme that computes coordinates independently and then reconstructs will hit this as an impossible input, not as a wrong answer. 2. **Ambiguous pairs.** Asking for `x` congruent to 1 modulo 8 and 5 modulo 12 is solvable - both are 1 modulo 4 - but the answers below 96 are `17, 41, 65, 89`, spaced exactly `24` apart. The pair identifies a class modulo 24, and reading it as an address below 96 silently conflates four values. A useful check on the arithmetic: the reachable-cell count and the uniqueness window are the same number, 24, and they must be - the `96` values land one-for-one onto `96 / 4 = 24` classes, each class filling one reachable cell. ## What it does not cost It is worth being exact about the damage, because it is easy to overstate. The reachable cells are **not** loaded unevenly: every reachable cell is hit by exactly four of the 96 values, so the distribution across the cells that exist is perfectly flat. The losses are the `72` cells that can never be used and the four-fold collision inside the ones that can. Skew is not among the symptoms. ## Restoring the property Three honest options, in the order they are usually reached for: - **Change one modulus** so the pair becomes coprime - `8` and `9` instead of `8` and `12` restores all `72` combinations and a `72`-step realignment period. - **Keep the pair and accept the smaller space**, sizing the scheme against `lcm(m, n)` rather than the product, and treating the pair as an address in a 24-cell space. - **Drop the redundancy**: since the shared factor means one coordinate already tells you part of the other, the pair is carrying less information than its size suggests, and a single modulus of `lcm(m, n)` carries the same information in one coordinate. ## The generalisation to watch With more than two coordinates the condition is **pairwise** coprimality. A trio like `6, 10, 15` has no factor common to all three, which tempts the eye, but each pair shares one, so the reconstruction fails on every pair in turn. Check pairs, never the whole set at once.

  • How many of the 96 pairs (a mod 8, b mod 12) are actually reachable, and why that number?
    24. Both coordinates must agree modulo `gcd(8, 12) = 4`, so once `a` is fixed only 3 of the 12 possible `b` values are legal, giving `8 * 3 = 24`. That matches `lcm(8, 12) = 24`, as it must: the 96 values fall into 24 classes of 4, one class per reachable pair.
  • Does a shared factor make the reachable addresses unevenly loaded?
    No - that is the tempting wrong answer. Each reachable pair is produced by exactly four of the 96 values, so the load across the cells that exist is flat. The costs are the 72 cells that are unreachable at all and the four-way ambiguity inside the rest, not skew.
  • With three moduli, is it enough that no single factor divides all three?
    No. The requirement is pairwise coprimality. Take 6, 10 and 15: no number above 1 divides all three, yet each pair shares a factor (2, 3 and 5 respectively), so every two-modulus subsystem is already constrained and the reconstruction does not work.

saying these in an interview costs you the question

  • Assumes any two moduli give a unique reconstruction
  • Says a shared factor merely wastes space with no ambiguity
  • Claims uniqueness is modulo the product regardless of the gcd
  • Blames a shared factor for uneven load across reachable addresses
  • Checks only that no factor divides all moduli, not each pair