skip to content

Bucketing keys by remainder modulo n collapses integers into residue classes: what exactly does that collapse preserve?

level: middleimportance: must knowfreq 62%

answer

  1. same remainder, same bucket
  2. n divides the difference
  3. classes are infinite sets
  4. plus and times are class-safe
  5. exponents are not operands

basics

~10 s

Addition, subtraction and multiplication survive: the class of a sum or product depends only on the input classes, never on which representatives you picked. Order, cancellation and the exponent position do not survive.

solid answer

~40 s

Congruence modulo `n` means `n` divides the difference: `a` and `b` land in the same bucket exactly when `n` divides `a - b`. That relation splits the integers into `n` residue classes, each an infinite set of integers sharing one remainder. The useful fact is that the arithmetic is **well defined on the classes**: if `a` is congruent to `a'` and `b` to `b'`, then `a + b` is congruent to `a' + b'` and `a * b` to `a' * b'`. So any expression built from addition, subtraction and multiplication with integer coefficients can be evaluated on representatives and still lands in the right class. What the collapse destroys is everything that reads magnitude: ordering, cancellation of a shared factor, and the exponent position, which counts multiplications rather than being multiplied.

go deeper

for a junior

Recall the definition in the divisibility form: two integers are congruent modulo n when n divides their difference, which is the same as sharing a remainder.

for a middle

Explain well-definedness: adding or multiplying representatives lands in the same class whichever representatives you pick, which is what makes reduction safe inside sums and products.

for a senior

Show where the collapse costs you in a running system - comparisons, cancellation and exponent handling all break, and a shared bucket proves only that the difference is a multiple of the modulus.

for a principal

Frame the choice: reducing by a modulus is a deliberate loss of information, so decide up front which questions must still be answerable after the collapse and keep the unreduced value where they are not.

## The definition, and the form worth reasoning with Two integers `a` and `b` are **congruent modulo n** (written `a = b (mod n)`, with `n` a positive integer) when `n` divides their difference, that is `a - b = kn` for some integer `k`. The equivalent everyday phrasing is that `a` and `b` leave the same remainder on division by `n`. Prefer the divisibility form when you argue: it is symmetric on its face and it never drags you into an argument about how a particular remainder convention treats negative inputs. Congruence modulo `n` is an **equivalence relation**. It is reflexive because `n` divides `0`; symmetric because `n` divides `a - b` exactly when it divides `b - a`; transitive because the sum of two multiples of `n` is a multiple of `n`. An equivalence relation partitions its set, so the integers split into exactly `n` disjoint **residue classes** modulo `n`. ## What a residue class actually is - A class is an **infinite set**, not a small number. The class of `3` modulo `10` contains `3`, `13`, `23`, `-7`, `-17` and so on forever. - The remainder `0..n-1` is just the conventional **representative** of the class, chosen because it is convenient to print. The class does not prefer it. - There are exactly `n` classes, and every integer is in exactly one of them. That is why reduction is a total function into a fixed set of buckets. - Two integers are in the same class precisely when their difference is a multiple of `n` - no weaker statement about them follows. ## The operations that survive the collapse The reason modular arithmetic is arithmetic at all is a single well-definedness result. Suppose `a = a' (mod n)` and `b = b' (mod n)`, so `a = a' + sn` and `b = b' + tn`. 1. **Addition.** `a + b = (a' + b') + (s + t)n`, so the difference from `a' + b'` is a multiple of `n`. 2. **Subtraction.** The same computation with a minus sign; every class also has an additive opposite, the class of `n - r`. 3. **Multiplication.** `a * b = a'b' + n(a't + b's + stn)`, and every term of that bracket is an integer, so `a * b` and `a' * b'` differ by a multiple of `n`. Because those three are safe, **any expression built from them with integer coefficients** - an integer polynomial in the inputs - is safe too. This is the licence behind every digit-sum divisibility rule, every weighted checksum, and every argument that a quantity's residue cannot change. ## What does not survive | operation | survives the collapse | why | |---|---|---| | addition, subtraction | yes | difference of results is a multiple of `n` | | multiplication | yes | the cross terms all carry a factor of `n` | | comparison, size, sign | no | `7` and `2` are congruent modulo `5` yet not the same size | | division or cancelling a shared factor | not in general | needs the factor to share no factor with `n` | | the exponent position | no | an exponent counts multiplications, it is not multiplied | | any arbitrary function of the integer | no | only expressions built from `+`, `-` and `*` are guaranteed | The exponent row is the one that catches people. In `x` raised to the power `e`, the **base** `x` may be replaced by any congruent integer, because raising to a power is repeated multiplication. The **exponent** `e` may not be reduced modulo `n`: it is a count of how many multiplications happen, not an operand of one. A rule for shrinking exponents does exist, and it uses a different modulus entirely - that belongs to the totient material, not here. ## Reading it back at the bucket Bucketing by remainder therefore guarantees exactly one direction: **equal keys always land together**, because equal integers are trivially congruent. It guarantees nothing in the other direction. Two keys sharing a bucket tell you only that their difference is a multiple of the bucket count; they need not be close, related, or similar in any other way, and a shared bucket is never evidence of equality. One extra consequence is worth carrying. If `m` divides `n`, then `a = b (mod n)` implies `a = b (mod m)`: `n` divides `a - b` and `m` divides `n`, so `m` divides `a - b`. Coarsening the modulus is safe; refining it is not. That is precisely why halving a bucket count keeps co-bucketed keys together while doubling it scatters them.

  • Why does subtraction survive the collapse while ordinary division does not?
    Subtraction is addition of an additive opposite, and every class has one: the class of `n - r` added to the class of `r` gives the class of `0`. Division asks for a multiplicative opposite instead, and only classes sharing no factor with `n` have one, so the operation is not defined across all classes.
  • If two keys share a bucket under modulus n, what follows under a different modulus m?
    In general nothing, with one exception: if `m` divides `n` it still holds, because `n` divides the difference and `m` divides `n`. The converse fails - agreeing modulo `m` says nothing about agreeing modulo a multiple of `m`.
  • Does knowing a key's class modulo n tell you anything about its size?
    No. A class contains arbitrarily large and arbitrarily negative integers, so the class fixes the difference from a representative as a multiple of `n` and nothing else. Any reasoning that compares magnitudes has to be done before the reduction, not after it.

saying these in an interview costs you the question

  • Treating congruent numbers as equal, so sizes compare the same way
  • Assuming any function of an integer respects congruence, not just sums and products
  • Reducing an exponent modulo n as if it were a coefficient
  • Reading a shared bucket as evidence that two keys are otherwise related
  • Thinking a class contains only its remainder rather than infinitely many integers