Back to the on-screen lesson ·
Every digit rule is one congruence about the number ten, and the same idea run backwards is an error-detecting code.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to derive a divisibility test from what ten is modulo the divisor, use the digit sum and the alternating digit sum to find a remainder rather than only to decide divisibility, say why no useful digit test exists for seven, split a test for a composite divisor into coprime parts, and choose a check digit so that a fixed congruence holds.
A number is divisible by 3 when its digits add to a multiple of 3. By 4 when its last two digits are. By 11 when the alternating sum of its digits is. These arrive in school as facts to memorise, in a list with no visible organisation, and the list stops at 11 for reasons nobody explains.
Every one of them is a single congruence about the number ten, and once that is seen the list stops being arbitrary: it becomes a short, complete classification of which divisors can have a digit test at all, and 7 turns out to be missing for a reason.
The digit sum of $n$ is the sum of its decimal digits. The alternating digit sum is taken from the units digit upwards with signs $+, -, +, -, \ldots$, so $1234$ gives $4 - 3 + 2 - 1 = 2$.
Casting out nines is the old arithmetic check: reduce both sides of a calculation modulo $9$ using digit sums and see whether they agree.
A check digit is an extra symbol appended to a code so that a fixed congruence holds. A transposition error is two adjacent symbols typed in the wrong order — the second commonest human error after a single wrong symbol, and the one a plain digit sum cannot detect.
Write $n = \sum_i d_i 10^i$ with digits $d_i$. Since congruence respects sums and products, $$n \equiv \sum_i d_i \,(10 \bmod m)^i \pmod m,$$ so the test for $m$ is decided entirely by what $10$ is modulo $m$. Three cases are useful and the rest are not.
$m$ divides a power of ten ($m = 2, 4, 5, 8, 10, 16, 20, 25, \ldots$). Then $10^k \equiv 0$ from some point on, and only the last $k$ digits survive. $4 \mid 100$, so the last two digits decide divisibility by $4$; $8 \mid 1000$, so the last three decide $8$.
$10 \equiv 1 \pmod m$, which happens for $m = 3$ and $m = 9$. Then every power of ten is $1$, so $n \equiv$ its digit sum. This is the test for $3$ and for $9$, and it is why they are the same test.
$10 \equiv -1 \pmod m$, which happens for $m = 11$. Then the powers of ten alternate $1, -1, 1, -1$, so $n \equiv$ its alternating digit sum.
Everything else. Modulo $7$, $10 \equiv 3$ and its powers run $3, 2, 6, 4, 5, 1$ before repeating — six different weights. A test exists ($n$ is congruent to the weighted sum with those weights) and nobody uses it, because it is no easier than dividing.
Composite divisors split by the Chinese remainder theorem: $6 = 2 \cdot 3$ with the parts coprime, so test for $2$ and for $3$ separately. $12 = 4 \cdot 3$ likewise. What does not work is testing for $2$ and $6$ to get $12$, because those parts are not coprime.
The base is not special. In base $b$, the digit-sum test works for $b - 1$ and its divisors, and the alternating-sum test for $b + 1$. Base ten gives $9$ and $3$, and $11$; base sixteen would give $15, 5, 3$ and $17$.
Another way: steps
Another way: example
Is $918291$ divisible by $9$? Digits add to $9 + 1 + 8 + 2 + 9 + 1 = 30$, and $3 + 0 = 3$, so the remainder is $3$: no. By $11$? Alternating from the units: $1 - 9 + 2 - 8 + 1 - 9 = -22 \equiv 0$, so yes. By $4$? The last two digits are $91$, which is not a multiple of $4$: no.
A divisibility test asks whether a congruence holds for a number that already exists. A check digit turns that round: a symbol is appended precisely so that the congruence will hold, and any later corruption is likely to break it.
The ISBN-10 scheme is the cleanest example. The ten digits $d_1, \ldots, d_{10}$ satisfy $$\sum_{i=1}^{10} (11 - i)\, d_i \equiv 0 \pmod{11},$$ with the last digit chosen to make that true — and written as X when it has to be $10$, which is why the character appears at all.
Two design choices are doing the work, and both matter.
The modulus is prime. Change one digit $d_i$ by an amount $e \ne 0$ and the weighted sum changes by $(11 - i)e$. Modulo a prime, a product of two non-zero residues is never zero, so the sum cannot stay at $0$: every single-digit error is caught. With modulus $10$ this fails — changing a digit weighted by $5$ by an amount of $2$ changes nothing — which is exactly why ISBN-10 uses $11$ and accepts the awkward X.
The digits are weighted. Swap $d_i$ and $d_j$ and the sum changes by $(j - i)(d_i - d_j)$, which modulo a prime is non-zero unless the two digits are equal. So every transposition is caught too. An unweighted sum is blind to transpositions entirely, since addition does not care about order — which is the one thing a plain casting-out-nines check cannot do.
What no check digit does is correct anything. It detects, with a known and provable class of errors caught, and then asks for the code to be retyped. Correcting errors needs more redundancy and different mathematics, and that is coding theory rather than this course.
Inventing a digit-sum test for 7. There is none of the useful kind. $10 \equiv 3 \pmod 7$, and the weights cycle through six values. Any rule offered for $7$ is either the full weighted sum or a subtraction trick that is not shorter than dividing.
Splitting a composite into parts that are not coprime. For $12$, test $4$ and $3$. Testing $2$ and $6$ passes $18$, which is not a multiple of $12$. The Chinese remainder theorem needs the parts coprime, and it is the theorem being used.
Starting the alternating sum at the wrong end. It runs from the units digit, with a plus. Starting at the left flips every sign, which changes the answer to its negative — harmless for a divisibility test, wrong for a remainder.
Expecting the digit sum to give the remainder for 3 as well as for 9. It does, but the digit sum has to be reduced modulo $3$, not modulo $9$. The tests agree on divisibility and disagree on remainders.
Thinking a check digit corrects errors. It detects them. A failed check means retype, not repair.
Is $4321 \times 1234 = 5332114$ plausible? Reduce each factor modulo $9$ by its digit sum: $4321 \to 10 \to 1$, and $1234 \to 10 \to 1$.
Reduce the inputs first.
So the product should be $\equiv 1 \cdot 1 = 1 \pmod 9$. The claimed answer has digit sum $5 + 3 + 3 + 2 + 1 + 1 + 4 = 19 \to 10 \to 1$.
The check passes.
The check passes, which is not the same as the answer being right — one error in nine survives it, and any error that is a multiple of $9$ does. The true product is $5332114$, so here it is right; but a transposed pair of digits would also have passed.
A passed check is evidence, not proof.
Take the four digits $3, 1, 4, 2$ and weight them $5, 4, 3, 2$, leaving weight $1$ for the check digit. The weighted sum so far is $15 + 4 + 12 + 4 = 35$.
The weights are what catch a transposition.
We need the total to be $\equiv 0 \pmod{11}$. Since $35 \equiv 2$, the check digit must be $\equiv -2 \equiv 9$.
One subtraction settles it.
So the code is $31429$. Change any one digit and the sum moves by a non-zero multiple of a non-zero weight, which modulo a prime cannot be $0$ — so the check fails and the error is caught.
Primality of the modulus is what makes that guarantee.
$10 \equiv -1 \pmod{11}$, so weight the digits from the units upwards with $+, -, +, -, +$.
The weights come from the powers of ten.
$2 - 6 + 0 - 3 + 7 = 0$.
Start at the units digit, with a plus.
So the remainder is $0$ and $73\,062$ is divisible by $11$; indeed $73\,062 = 11 \cdot 6642$.
For $8516$, give the digit sum, the remainder on division by $9$, the alternating digit sum taken from the units digit, and the remainder on division by $11$.
| Value | |
|---|---|
| Digit sum | |
| Remainder on division by $9$ | |
| Alternating digit sum | |
| Remainder on division by $11$ |
A whole number's digits add up to $1$. What is its remainder on division by $9$?
Answer:
Is this test correct: a number is divisible by $4$ when its last two digits are?
Match each divisor to the feature of the decimal expansion that decides divisibility by it.
| the last two digits | the last three digits | the sum of all the digits | the alternating sum of the digits | |
|---|---|---|---|---|
| $4$ | ||||
| $8$ | ||||
| $9$ | ||||
| $11$ |
Mark the remainder of $5537$ on division by $11$. The line runs from $0$ to $11$.
0 |——————————| 11
Mark the position with a cross, then write the value:
A four-digit code is written $1\,3\,4\,c$, where the last digit $c$ is chosen so that all four digits add to a multiple of $9$. What is $c$?
check digit a
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
For $5537$, give the digit sum, the remainder on division by $9$, the alternating digit sum taken from the units digit, and the remainder on division by $11$.
| Value | |
|---|---|
| Digit sum | |
| Remainder on division by $9$ | |
| Alternating digit sum | |
| Remainder on division by $11$ |
You can derive and apply the digit tests, and explain each from one congruence about ten. Say in your own words why a check-digit scheme uses a prime modulus and weights its digits. Next: what happens to a residue when it is raised to a power.
9. Your turn: find the remainder of $73\,062$ on division by $11$, step 3