A validator tests divisibility by nine by summing a number's decimal digits: which congruence makes that legitimate?
answer
- ask what the base is congruent to
- ten leaves remainder one
- every power of ten collapses to one
- the number inherits its digit sum's class
- nine divides ten minus one
basics
~20 sTen is congruent to 1 modulo 9, so every power of ten is congruent to 1 as well, which makes any number congruent to the sum of its digits modulo 9. The digit test is that congruence, not a decimal coincidence.
solid answer
~40 sWrite the number positionally: it is a sum of `d_i * 10^i` over its digits. Because `10 = 1 (mod 9)` and multiplication is well defined on residue classes, `10^i = 1^i = 1 (mod 9)` for every position, so each digit contributes its own value and the whole number is congruent to `d_0 + d_1 + ...` modulo 9. The same argument with `10 = 1 (mod 3)` gives the rule for 3. The rule generalises by asking what the **base** is congruent to: moduli dividing `10 - 1` get a plain digit sum, and moduli dividing `10 + 1` get an alternating one, because there `10 = -1` and the powers flip sign. Nothing else gets a constant-weight rule.
go deeper
Recall the fact and its one-line reason: ten leaves remainder one modulo nine, so a number and its digit sum sit in the same class.
Derive it from the positional expansion, and say what decides whether a rule exists - whether the modulus divides the base minus one, or the base plus one.
Draw the practical conclusion: equal weights make reordered digits and a zero-for-nine swap invisible, so a digit sum is a divisibility test rather than an error check.
Generalise the lever rather than the trick - the rule is about the base's residue, so any change of base or modulus must be re-derived instead of assumed to carry over.
## The positional expansion is the whole argument A decimal numeral is shorthand for a sum: the digits `d_k ... d_1 d_0` denote `d_k * 10^k + ... + d_1 * 10 + d_0`. That expression is built entirely from addition and multiplication with integer coefficients, which is exactly the class of expressions that survives reduction into residue classes. So you may replace `10` anywhere in it by any integer congruent to `10`, and the value's class is unchanged. Modulo 9 the replacement is maximally convenient: `10 - 1 = 9`, so `10 = 1 (mod 9)`. Then `10^i = 1^i = 1 (mod 9)` for every position `i`, and the sum collapses to `d_k + ... + d_1 + d_0`. The number and its digit sum sit in the same residue class modulo 9, which is why one is divisible by 9 exactly when the other is. ## What determines whether a rule exists The test is not about the modulus in isolation; it is about how the modulus relates to the **base**. - If the modulus divides `base - 1`, then `base = 1` and every positional weight collapses to `1`: a **plain digit sum**. For base ten that gives 9 and its divisor 3. - If the modulus divides `base + 1`, then `base = -1` and the weights become `1, -1, 1, -1, ...`: an **alternating digit sum**. For base ten that gives 11. - Otherwise the powers of the base cycle through several residues and the rule needs a repeating pattern of weights, which is why no memorable one-line test exists. | modulus | 10 is congruent to | positional weights | resulting rule | |---|---|---|---| | 3 | 1 | 1, 1, 1, 1, ... | plain digit sum | | 9 | 1 | 1, 1, 1, 1, ... | plain digit sum | | 11 | -1 | 1, -1, 1, -1, ... | alternating digit sum | | 7 | 3 | 1, 3, 2, 6, 4, 5, repeating | weighted sum with period six | For 7, trace the powers directly: `10^0 = 1`, `10^1 = 3`, `10^2 = 2`, `10^3 = 6`, `10^4 = 4`, `10^5 = 5`, `10^6 = 1` again. Six distinct weights before the cycle repeats. A valid rule exists - multiply the digits by that repeating pattern and sum - but nobody remembers it, and that is a consequence of the arithmetic rather than of tradition. ## What the rule actually computes A point often missed: the digit sum does not merely answer yes or no. It is congruent to the number, so it reports the **whole residue class**. Summing the digits of `1234` gives `10`; summing again gives `1`, and `1234` does indeed leave remainder 1 on division by 9. The only quirk is presentation: repeatedly summing a non-zero multiple of 9 lands on `9` rather than `0`, because `9` is the representative the process reaches for the zero class. This also explains why digit-sum checks catch so little as error detection. Since the weights are all `1`, reordering the digits changes nothing at all, and changing a `0` into a `9` shifts the sum by exactly `9`, which is congruent to `0`. Both errors are invisible to a modulo-9 digit sum. That is a property of the weights and the modulus, not a flaw in the implementation. ## Two directions worth keeping straight 1. The rule says the number and the digit sum are **congruent**, so it is an if-and-only-if for divisibility: the number is divisible by 9 exactly when its digit sum is. It is not a one-way heuristic. 2. The rule is tied to base ten. Change the base and the arithmetic moves with it - a digit sum then tests divisors of the new base minus one, and carries no guarantee for 9 unless 9 happens to divide that. Reasoning that survives the change is reasoning about `base - 1`, not about the digit `9`.
- Which moduli get an alternating digit-sum rule instead, and why?Those dividing `10 + 1`, so 11 in base ten. There `10 = -1 (mod 11)`, hence `10^i = (-1)^i`, and the positional weights alternate between `+1` and `-1`. The number is therefore congruent to `d_0 - d_1 + d_2 - ...` modulo 11.
- Does the digit sum give the remainder itself, or only whether it is zero?The remainder itself. The digit sum is congruent to the number modulo 9, so folding it down to a single digit yields the remainder, with `9` printed for the zero class. The rule is a class computation that happens to be used most often for the divisibility case.
saying these in an interview costs you the question
- Treating the digit-sum rule as a quirk of decimal notation with no reason
- Expecting a constant-weight digit rule for every divisor, including seven
- Applying the alternating sum to nine instead of eleven
- Thinking the digit sum reports the quotient rather than the remainder class
- Assuming the rule still tests nine after the digits are rewritten in another base