skip to content

You are choosing the modulus and the weights for an account-number check digit: what does the modulus decide?

level: principalimportance: nice to knowfreq 26%

answer

  1. undetected means the change vanishes
  2. an error shows up as a difference
  3. both signatures are small products
  4. zero divisors hide mistakes
  5. prime modulus, weights differing per position

basics

~20 s

The modulus decides which mistakes can hide. A prime modulus above the digit range has no zero divisors, so with weights that differ by position no single-digit change and no adjacent transposition can leave the weighted sum's class unchanged.

solid answer

~50 s

A check scheme fixes weights `w_i` and accepts a number when the weighted sum of its digits is congruent to `0` modulo `n`. An error is undetected exactly when the **change** it makes to that sum is congruent to `0`. A single wrong digit at position `i` changes the sum by `w_i * e`, with the error `e` between `-9` and `9` and non-zero. Swapping adjacent digits changes it by `(w_i - w_{i+1}) * (d_{i+1} - d_i)`, again a product of two values bounded by 9. Modulo a prime larger than 9 there are no zero divisors, so neither product can vanish provided no weight is congruent to `0` and neighbouring weights differ. Modulo 10 there are zero divisors - a weight of 2 with an error of 5 gives `10`, invisible - and equal weights make every transposition invisible whatever the modulus.

code

pseudocode · 11 lines
pseudocode
// MOD is prime and greater than 9
// weight[i] is never 0 mod MOD, and weight[i] != weight[i+1] mod MOD

total = 0
for i from 0 to length(digits) - 1:
    total = total + weight[i] * digits[i]

if (total mod MOD) == 0:
    accept the number
else:
    reject the number

go deeper

for a junior

Recall what a check digit is for: it is computed so the weighted sum of the digits leaves remainder zero, and verification recomputes that remainder.

for a middle

Derive the two error signatures - a mistyped digit shifts the sum by weight times error, a transposition by the weight difference times the digit difference - and say when each vanishes.

for a senior

Argue the modulus from zero divisors, and name the concrete failures a composite modulus admits, such as a weight of two hiding an error of five modulo ten.

for a principal

Own the trade the arithmetic cannot settle: symbol budget, the error profile of the real input path, the fact that the scheme stops accidents only, and the reissue cost of ever changing it.

## Restate the goal as a congruence question A check digit is appended so that the whole number satisfies `w_0*d_0 + w_1*d_1 + ... = 0 (mod n)` for a fixed weight per position. Verification recomputes the weighted sum and accepts on residue zero. The design question is therefore not "how strong is the check" in the abstract, but: **for which corruptions is the change to the weighted sum congruent to zero?** Those, and only those, slip through. This reframing is what makes the choice decidable, because the two dominant human errors have exact algebraic signatures. ## The two error signatures 1. **A single mistyped digit** at position `i`: the digit becomes `d_i + e` with `e` non-zero and `|e| <= 9`. The weighted sum moves by `w_i * e`. Undetected exactly when `n` divides `w_i * e`. 2. **A transposition of adjacent digits** at positions `i` and `i+1`: the sum moves from `w_i*d_i + w_{i+1}*d_{i+1}` to `w_i*d_{i+1} + w_{i+1}*d_i`, a change of `(w_i - w_{i+1}) * (d_{i+1} - d_i)`. Undetected exactly when `n` divides that product. Both factors are non-zero and bounded by 9 whenever the swapped digits differ and neighbouring weights differ. Both signatures are a **product of two small non-zero numbers**, so the design question collapses to one property of the modulus: can a product of two non-zero small factors be congruent to zero? ## Why zero divisors are the whole story Modulo a prime `p` there are no zero divisors: if `p` divides a product, it divides one of the factors. Choose `p > 9` and both signatures become impossible, as long as no weight is congruent to `0` (which would make a position unchecked) and no two neighbouring weights are congruent (which would make their difference vanish). Modulo a composite the property fails, and it fails at small numbers. Modulo 10, `2 * 5 = 10` is congruent to `0`, so a position weighted `2` hides any error of exactly `5` - mistyping a `1` as a `6`, for instance. That is not a rare case; it is a whole family of everyday typos. | modulus and weights | single-digit errors | adjacent transpositions | cost | |---|---|---|---| | 9, all weights equal | misses a 0 for 9 swap, since 9 is congruent to 0 | all missed | cheapest, weakest | | 10, all weights equal | all caught | all missed | reordering is invisible | | 10, varied weights | some missed via zero divisors 2 and 5 | some missed | check value fits one digit | | 11, varied weights | all caught | all caught | needs an eleventh symbol | | a prime above 9, varied weights | all caught | all caught | check value needs two digits | ## The judgment the table does not make for you The arithmetic says a prime modulus above 9 with position-varying weights dominates on detection. The design still has to pay for it, and that is where the decision actually lives: - **Symbol budget.** A modulus of `n` needs `n` distinct check values. With `n = 11` one value does not fit in a decimal digit, so schemes either print a non-digit symbol or refuse to issue the numbers that need it. A larger prime needs two check characters and lengthens every number a human must read aloud. - **Which errors your population actually makes.** Adjacent transposition and single mistyping dominate hand-entered numbers; if the input path is machine-to-machine, neither is the risk and a check digit is the wrong instrument entirely. - **What the check is not.** A check digit detects accident, never intent. The weights and the modulus are public by necessity, so anyone can compute a valid check value for any number they like. Claiming a check digit as a tamper control is a category error, and no modulus repairs it. - **Stability.** The modulus and weights are part of the published format. Changing either invalidates every issued number, so this is a decision made once, at design time, with the cost of being wrong measured in reissues. ## The rule of thumb that survives Pick the modulus first, and pick it prime and larger than the largest possible single-digit error. Then make sure no weight is congruent to zero and no two adjacent weights are congruent. Everything else - how many characters the check occupies, whether a non-decimal symbol is acceptable, whether the scheme is worth having at all - is a trade against legibility and issuance, not against arithmetic.

  • Why does a modulus of 11 force an extra symbol into the format?
    The check value ranges over 11 residues, one more than the ten decimal digits can express. A scheme must therefore print one residue as a non-digit symbol, or refuse to issue the numbers whose check value lands on it. That is a presentation cost bought purely to gain a prime modulus.
  • Which single-digit error does a plain digit sum modulo 9 miss?
    Writing a `0` as a `9` or the reverse: the sum changes by exactly `9`, which is congruent to `0` modulo 9, so the class is unchanged. Equal weights also mean every reordering of the digits is invisible, since the sum does not depend on position at all.
  • If the modulus is prime, do the weights still matter?
    Yes. A weight congruent to zero leaves that position unchecked entirely, and two neighbouring weights that are congruent make their difference vanish, so adjacent transpositions there go undetected. The prime modulus removes zero divisors; it cannot supply the variation the weights are responsible for.

saying these in an interview costs you the question

  • Choosing modulus ten just because the digits are decimal
  • Using equal weights, which leaves every transposition invisible
  • Presenting a check digit as protection against deliberate tampering
  • Assuming a prime modulus works regardless of the weights chosen
  • Believing a longer account number detects more errors by itself
  • Treating an undetected error as bad luck rather than a zero divisor