Why can you reduce mod m after each add and multiply in a running checksum, but not after a divide?

## The streaming setting An ingestion pipeline receives chunks and must fold each chunk's identifier into a running checksum. The constraints are the ones streaming always imposes: one pass, no buffering of the whole stream, and a fixed amount of state. Modular arithmetic is what makes that possible — the running value is kept reduced, so the state is a single machine word regardless of how many chunks arrive, and no arbitrary-precision arithmetic is needed. That works because reduction *commutes* with the operations the fold uses. ## What "distributes" actually means here The precise statement is about congruence. Write `a ≡ a' (mod m)` when `a` and `a'` leave the same remainder. Then: - if `a ≡ a'` and `b ≡ b'`, then `a + b ≡ a' + b'` - if `a ≡ a'` and `b ≡ b'`, then `a - b ≡ a' - b'` - if `a ≡ a'` and `b ≡ b'`, then `a * b ≡ a' * b'` So replacing any operand by its residue at any point leaves the final residue untouched. This is an exact algebraic identity, not an approximation, and it is what licenses reducing inside the loop rather than at the end. The structure has a name — the residues under these three operations form a ring — and the three operations listed are exactly the ring operations. Division is conspicuously absent. ## Why division falls out Reduction throws information away: `6`, `10`, `14` and `2` are all the same residue mod 4. Addition and multiplication are insensitive to that loss — every representative of a class produces an answer in the same output class. Division is not. Take `m = 4`: - `6 mod 4 = 2`, and truncating `2 / 2 = 1`. - But `6 / 2 = 3`, and `3 mod 4 = 3`. One is 1, the other is 3. The answer depended on which representative you started from, so the operation is not defined on residue classes at all. Picking a prime modulus does not rescue truncating division either: with `m = 5`, `6 mod 5 = 1`, and truncating `1 / 2 = 0`, while `6 / 2 = 3` reduces to 3. ## What replaces division Dividing by `b` becomes multiplying by `b`'s **modular inverse** — the residue `b_inv` satisfying `b * b_inv ≡ 1 (mod m)`. Then `a * b_inv` behaves as `a / b` does, and because it is a multiplication it slots back into the safe list above. The inverse does not always exist. It exists exactly when `b` and `m` share no common factor greater than 1. With `m = 4`, the residue 2 has no inverse: `2 * x` is always even, never 1 mod 4. With a **prime** modulus every nonzero residue is coprime to it, so every nonzero residue has an inverse — which is the practical reason counting pipelines and checksums standardize on a prime modulus rather than a round one. Even then, zero has no inverse, so dividing by a value congruent to zero is still undefined, and code must handle that case rather than assuming primality made it disappear. ## Two more things that do not survive reduction **Ordering.** Residues carry no information about the size of the originals. If chunk A's fold is 900000000 and chunk B's is 5, that says nothing about which underlying quantity was larger — reduction wraps. Any comparison, sort, or "is this bigger than the threshold" check must run on unreduced values. **Equality in the strong sense.** Equal residues mean the originals are *congruent*, not equal. Two distinct chunk streams can fold to the same checksum. That is fine for a checksum, whose job is cheap mismatch detection, but it means a match is evidence, not proof, and code must not treat it as identity. ## In review The patterns worth flagging: any `/` applied to values that are already reduced; averaging a modular accumulator by dividing by the count; comparing or sorting reduced values; and folding in an incoming value that was never reduced itself, so the multiply can exceed the width bound. The first two are the same bug wearing different clothes, and both produce plausible-looking numbers that are simply wrong.