skip to content

Under the Chinese remainder theorem, why do a record's remainders under two coprime moduli pin exactly one value below their product?

level: seniorimportance: must knowfreq 55%

answer

  1. a pair of coordinates names a value
  2. same pair means the difference divides by both
  3. coprime turns both into the product
  4. equal counts make it onto as well
  5. uniqueness only up to the product

basics

~20 s

Two values with the same pair of remainders differ by a multiple of both moduli, and for coprime moduli that forces a multiple of their product, so at most one such value lies below the product. Counting shows every pair occurs.

solid answer

~40 s

Take coprime moduli `m` and `n` and map each value `x` to the pair `(x mod m, x mod n)`. If two values share a pair, their difference is divisible by `m` and by `n`; since `gcd(m, n) = 1`, it is divisible by `m*n`. So no two of the `m*n` values in `0..m*n-1` collide - the map is one-for-one. There are also exactly `m*n` possible pairs, so a one-for-one map between two equal finite sets is onto as well: **every** pair occurs, for exactly one value. Uniqueness is *modulo the product*: adding `m*n` changes neither remainder, so the answer is a residue class, not a single integer.

code

pseudocode · 7 lines
pseudocode
// requires gcd(m, n) = 1
function combine(a, m, b, n):
    u = inverse(m mod n, n)        // exists exactly because gcd(m, n) = 1
    t = ((b - a) * u) mod n        // normalise into 0 .. n-1
    return (a + m * t) mod (m * n)

// combine(5, 8, 2, 9) -> 29 ; 29 mod 8 = 5, 29 mod 9 = 2

go deeper

for a junior

Grasp the shape first: two remainders under two moduli can act as a pair of coordinates naming one value, in the way a row and a column name one cell. When that works is the next step.

for a middle

Explain the collision argument: two values with the same pair differ by a multiple of both moduli, which coprimality turns into a multiple of the product. Then count pairs to get existence for free.

for a senior

Reconstruct a value, name where the inverse came from, and say plainly that uniqueness is modulo the product - so an identifier space larger than that product must collide.

for a principal

The lever is that coprime coordinates stay independent and realign only after their product. Sizing that product against the identifier space, before anything is built on the addressing, is the decision worth owning.

## The statement **Chinese remainder theorem, two-modulus form:** if `gcd(m, n) = 1`, then for any remainders `a` in `0..m-1` and `b` in `0..n-1` the system `x` congruent to `a` modulo `m`, and `x` congruent to `b` modulo `n` has a solution, and the solution is **unique modulo `m*n`**. Read as an addressing scheme: a pair of coordinates - say a shard index modulo 8 and a rotation slot modulo 9 - names one value, and the naming does not repeat until `72` values have gone by. ## Why no two values collide Suppose `x` and `y` produce the same pair. Then `m` divides `x - y` and `n` divides `x - y`. A number divisible by both is divisible by their least common multiple, and for coprime moduli `lcm(m, n) = m*n`. So `x - y` is a multiple of `m*n`, and two distinct values in the window `0..m*n-1` cannot differ by that much. The map is injective. **This is the exact step that coprimality buys.** With `m = 8` and `n = 12` the same argument only yields a multiple of `lcm(8, 12) = 24`, which is far short of `96` - and the uniqueness claim collapses with it. ## Why every pair is reachable There are `m*n` values in the window and `m*n` possible pairs. An injective map between finite sets of equal size is necessarily onto - a pigeonhole argument in its cleanest form. So existence comes free from uniqueness; there is no separate construction to believe. The map is a one-for-one correspondence between residues modulo `m*n` and pairs of residues. ## Reconstructing the value The correspondence is constructive. Write `x = a + m*t` - this satisfies the first congruence for any whole `t` - and then choose `t` to satisfy the second: 1. `a + m*t` must be congruent to `b` modulo `n`, so `m*t` is congruent to `b - a` modulo `n`. 2. Because `gcd(m, n) = 1`, the residue `m` is invertible modulo `n`; call that inverse `u` (taking it as a given primitive here). 3. Then `t = ((b - a) * u) mod n`, and `x = (a + m*t) mod (m*n)`. Worked on the shard-and-slot pair `a = 5` with `m = 8`, `b = 2` with `n = 9`: the inverse of 8 modulo 9 is 8, since `8 * 8 = 64 = 63 + 1`. So `t = ((2 - 5) * 8) mod 9 = (-24) mod 9 = 3`, and `x = 5 + 8 * 3 = 29`. Check: `29 mod 8 = 5` and `29 mod 9 = 2`. The next value with the same pair is `29 + 72 = 101`. Notice where coprimality entered the construction: it is precisely what makes step 2 possible. No inverse, no reconstruction. ## What the correspondence is good for - **Independent coordinates.** Two coprime coordinates can be read and reasoned about separately, and together they lose nothing: the pair carries exactly as much information as the value. - **A long realignment period.** The pair repeats only after `m*n` steps, so a calendar built on coprime cycles realigns as rarely as the moduli allow. - **Splitting a computation.** Arithmetic modulo `m*n` can be carried out separately modulo `m` and modulo `n` and recombined, since the correspondence respects both addition and multiplication. Two small computations replace one large one. - **Multiplicativity of the totient.** A value is coprime to `m*n` exactly when it is coprime to each of `m` and `n`, so the correspondence restricts to the coprime residues and yields `phi(m*n) = phi(m)*phi(n)` for coprime arguments. ## The boundaries worth stating aloud Uniqueness is modulo the product, never absolute: `29`, `101` and `173` all present as `(5, 2)`. If the identifier space is larger than `m*n`, two identifiers are guaranteed to share an address, and no cleverness in the reconstruction avoids it. The theorem also extends to more than two moduli, but the requirement is **pairwise** coprimality, not merely that no single prime divides all of them. Three moduli `6, 10, 15` share no common factor across all three, yet every pair shares one, and the theorem does not apply.

  • Does the theorem extend to three moduli, and what exactly must hold?
    Yes, with **pairwise** coprimality, and then the solution is unique modulo the product of all three. Having no single factor common to all three is not enough: 6, 10 and 15 have no common divisor above 1, yet each pair shares one, and the reconstruction fails. Check every pair, not the whole set.
  • The reconstructed value came out as 29 for the pair (5, 2). Which other values present as that same pair?
    Exactly `29 + 72k` for whole `k` - so 29, 101, 173 and so on, and 29 - 72 going the other way. Adding the product changes neither remainder, so the answer is a residue class modulo 72 rather than a single integer. The window `0..71` is what makes 29 the representative.
  • Why is the pair of remainders no less informative than the value itself?
    Because the map from residues to pairs is a one-for-one correspondence on `0..m*n-1`: distinct values give distinct pairs, and every pair is used. Nothing is discarded, so the value can always be recovered - which is why arithmetic can be done coordinate-wise and recombined at the end.

Two gears with 8 and 9 teeth: read off which tooth of each is at the mark and you know exactly where in the cycle you are, because the same pair of teeth does not meet again for 72 steps. Give them 8 and 12 teeth and the pair repeats after 24, so the reading is ambiguous.

saying these in an interview costs you the question

  • Thinks coprimality of the moduli is a convenience, not a requirement
  • Claims the reconstructed value is unique as an integer, not modulo the product
  • Believes some remainder pairs are simply unreachable under coprime moduli
  • Treats the pair as lossy, a fingerprint rather than a full address
  • Extends it to three moduli with no common factor across all three