Adding up the digits of a number tells you whether divides it. Why should the digits know anything about , and which other divisors can be read off the digits the same way?

Discrete Mathematics and Proof

Where the divisibility tests come from

Adding up the digits of a number tells you whether 9 divides it. Why should the digits know anything about 9, and which other divisors can be read off the digits the same way?

You need

Congruence modulo n and its arithmeticDiscrete Mathematics and Proof Divisibility rulesGrade 4

Where you are 7 in Modular arithmetic

Logic, proof and discrete math6

Introductory number theory8

Modular arithmetic7

Congruence modulo n and its arithmetic Powers modulo n

Where the divisibility tests come from

Fermat's little theorem Modular inverses and linear congruences ▾ Show all 7 (2 more)

When you reach for it

Two sets of tests are already familiar. The tests for 2, 5 and 10 read only the last digit. The tests for 3 and 9 add up all the digits, and showed why with bags of ten: each ten is a group of nine and one over. This lesson proves those tests with congruences, and the same proof produces new tests: an alternating sum for 11, sums of three-digit blocks for 7 and 13, and a check on a long multiplication. Reach for it when a remainder or a divisibility is wanted for a number given by its digits.

The procedure

Every positive integer n has a base-ten expansion n = d_k 10^k + \cdots + d_1 10 + d_0 with digits d_i \in \{0, \dots, 9\} (Numbers in other bases). Write

\begin{aligned} S(n) &= d_0 + d_1 + \cdots + d_k, \\ A(n) &= d_0 - d_1 + d_2 - \cdots + (-1)^k d_k \end{aligned}

for the digit sum and the alternating digit sum. In A(n) the ones digit always carries a plus sign. Every test below comes from one move: find a power of 10 that is congruent to 1 or to -1 modulo m, and use the replacement rule (Corollary 4 of Congruence modulo n and its arithmetic) to put that small number in place of the power.

Theorem 1 (nine and three). For every positive integer n, n \equiv S(n) \pmod{9} and n \equiv S(n) \pmod{3}. So n and S(n) leave the same remainder on division by 9, and on division by 3; in particular 9 \mid n exactly when 9 \mid S(n), and likewise for 3.

Proof. Since 10 - 1 = 9, 10 \equiv 1 \pmod{9}. By the replacement rule, 10^i \equiv 1^i = 1 \pmod{9} for every i \ge 1, and 10^0 = 1 as well. Replacing each power in the expansion,

\begin{aligned} n = \sum_{i=0}^{k} d_i 10^i &\equiv \sum_{i=0}^{k} d_i \cdot 1 \\ &= S(n) \pmod{9}. \end{aligned}

Because 3 \mid 9, a congruence modulo 9 holds modulo 3 too (Example 3 of Congruence modulo n and its arithmetic). Congruent numbers have equal remainders (Theorem 1 there), and a number is divisible by m exactly when its remainder is 0. \square

Theorem 2 (eleven). For every positive integer n, n \equiv A(n) \pmod{11}.

Proof. Since 10 + 1 = 11, 10 \equiv -1 \pmod{11}, so 10^i \equiv (-1)^i \pmod{11}, which is 1 for even i and -1 for odd i. Replacing each power gives n \equiv \sum d_i (-1)^i = A(n) \pmod{11}. \square

Theorem 3 (blocks). Cut the digits of n into blocks of j digits from the right, B_0 the last j digits, B_1 the next j, and so on, so that n = B_0 + B_1 10^j + B_2 10^{2j} + \cdots (the regrouping in Numbers in other bases).

If 10^j \equiv 1 \pmod{m}, then n \equiv B_0 + B_1 + B_2 + \cdots \pmod{m}.
If 10^j \equiv -1 \pmod{m}, then n \equiv B_0 - B_1 + B_2 - \cdots \pmod{m}.

Proof. Replace 10^j by 1, or by -1, in n = \sum_i B_i (10^j)^i, exactly as before. \square

Theorems 1 and 2 are the case j = 1. Also 100 \equiv 1 \pmod{99}, 100 \equiv -1 \pmod{101}, 1000 \equiv 1 \pmod{999} and 1000 \equiv -1 \pmod{1001}. Every divisor of a modulus inherits its congruences, so the factorizations

\begin{aligned} 99 &= 9 \cdot 11, \\ 999 &= 27 \cdot 37, \\ 1001 &= 7 \cdot 11 \cdot 13 \end{aligned}

turn these into tests for 11 again, for 27 and 37, and, most usefully, for 7 and 13: the alternating sum of three-digit blocks has the same remainder as n modulo 7, 11 and 13 at once. (Factoring 1001 is done in Every number has exactly one prime factorization.)

Tests from the last digits. When m \mid 10^j the tail is all that matters, and Numbers in other bases proves it: 4 and 25 divide n exactly when they divide the number formed by its last two digits, and 8 when it divides the number formed by its last three.

Casting out nines. Suppose ab = c. By Theorem 1 and the multiplication rule,

\begin{aligned} S(c) \equiv c &= ab \\ &\equiv S(a)\,S(b) \pmod{9}. \end{aligned}

By the contrapositive, if S(c) \not\equiv S(a)\,S(b) \pmod{9}, then c \ne ab. This is casting out nines, a check on a long multiplication using only digit sums. It is one-way: any wrong answer that differs from the right one by a multiple of 9 agrees too. Swapping two adjacent digits d_{i+1} and d_i changes a number by (d_i - d_{i+1}) 10^{i+1} + (d_{i+1} - d_i) 10^i = 9 (d_i - d_{i+1}) 10^i, a multiple of 9, so casting out nines never catches a swapped pair. The same check with A and modulus 11, casting out elevens, does catch it (exercise 16).

Other bases. In base b, b \equiv 1 \pmod{b - 1} and b \equiv -1 \pmod{b + 1}, so a base-b numeral’s digit sum has the same remainder as the number modulo b - 1, and its alternating digit sum the same remainder modulo b + 1.

Worked examples

Example 1

A remainder from a digit sum

Find the remainders of 5{,}082{,}736 on division by 9 and by 3.

Solution

By Theorem 1 the number is congruent to its digit sum, 5 + 0 + 8 + 2 + 7 + 3 + 6 = 31, modulo 9 and modulo 3. The digit sum may be reduced the same way: 31 \equiv 3 + 1 = 4. So 5{,}082{,}736 \equiv 4 \pmod{9}, remainder 4. Modulo 3, 4 = 3 + 1 \equiv 1, so the remainder on division by 3 is 1. Check: 5{,}082{,}736 = 9 \cdot 564{,}748 + 4.

Example 2

The alternating sum for 11

Show that 918{,}082 is divisible by 11.

Solution

By Theorem 2, read the digits from the right with signs +, -, +, \dots, the place values modulo 11.

Figure 1Modulo 11 every place value is 1 or -1, so 918{,}082 is congruent to 2 - 8 + 0 - 8 + 1 - 9 = -22.

\begin{aligned} A(918{,}082) &= 2 - 8 + 0 - 8 + 1 - 9 \\ &= -22 = (-2) \cdot 11. \end{aligned}

So 918{,}082 \equiv -22 \equiv 0 \pmod{11}, and 11 \mid 918{,}082. Indeed 918{,}082 = 11 \cdot 83{,}462.

Example 3

Seven, eleven and thirteen in one computation

Decide which of 7, 11 and 13 divide 627{,}354, and find the remainder for any that does not.

Solution

Use Theorem 3 with j = 3. Since 1000 = 1001 - 1, 1000 \equiv -1 \pmod{1001}, and because 7, 11 and 13 each divide 1001, the same congruence holds modulo each of them. The blocks from the right are 354 and 627.

Figure 2Modulo 1001, the place of the left block is worth 1000 \equiv -1, so 627{,}354 \equiv 354 - 627 = -273.

\begin{aligned} 627{,}354 &= 627 \cdot 1000 + 354 \\ &\equiv -627 + 354 = -273. \end{aligned}

Now 273 = 3 \cdot 91 = 3 \cdot 7 \cdot 13, so 7 \mid 273 and 13 \mid 273, and therefore 7 \mid 627{,}354 and 13 \mid 627{,}354. Modulo 11, 273 = 24 \cdot 11 + 9, so -273 \equiv -9 \equiv 2 \pmod{11}: 11 does not divide it, and the remainder is 2. Theorem 2 agrees: A(627{,}354) = 4 - 5 + 3 - 7 + 2 - 6 = -9 \equiv 2. Check: 627{,}354 = 7 \cdot 89{,}622 = 13 \cdot 48{,}258.

Example 4

Two-digit blocks for 99 and 101

Find the remainders of 48{,}257{,}163 on division by 99 and by 101, and deduce its remainders on division by 9 and by 11.

Solution

The two-digit blocks from the right are 63, 71, 25, 48. Since 100 \equiv 1 \pmod{99}, Theorem 3 gives

\begin{aligned} 48{,}257{,}163 &\equiv 63 + 71 + 25 + 48 = 207 \\ &= 2 \cdot 99 + 9 \pmod{99}, \end{aligned}

remainder 9. Since 100 \equiv -1 \pmod{101}, the alternating block sum gives 63 - 71 + 25 - 48 = -31, and -31 + 101 = 70, so the remainder is 70.

Both 9 and 11 divide 99, so the congruence passes down: 9 divides the number, and modulo 11 the remainder is 9. Theorems 1 and 2 agree: the digit sum is 36, and A = 3 - 6 + 1 - 7 + 5 - 2 + 8 - 4, which is -2 \equiv 9 \pmod{11}.

Example 5

Missing digits

Find every pair of digits a, b for which (6\,a\,4\,9\,b)_{10}, the number with digits 6, a, 4, 9, b in that order, is divisible by 99.

Solution

The two-digit blocks from the right are (9b)_{10} = 90 + b, then (a4)_{10} = 10a + 4, then 6. By Theorem 3 with 100 \equiv 1 \pmod{99}, the number is congruent to

\begin{aligned} &(90 + b) + (10a + 4) + 6 \\ &= 100 + 10a + b \\ &\equiv 1 + 10a + b \pmod{99}. \end{aligned}

So the condition is 99 \mid 1 + 10a + b. Since 0 \le 10a + b \le 99, the number 1 + 10a + b lies between 1 and 100, where the only multiple of 99 is 99. Hence 10a + b = 98: a = 9, b = 8, and the only such number is 69{,}498 = 99 \cdot 702.

Example 6

What casting out nines can and cannot see

Oyinda multiplies 4{,}817 \cdot 2{,}953 and gets 14{,}224{,}601. (a) Check this by casting out nines. (b) Show that 14{,}226{,}401, the same digits with one adjacent pair swapped, also passes. (c) Show that casting out elevens separates the two.

Solution

(a) S(4{,}817) = 20 \equiv 2 and S(2{,}953) = 19 \equiv 1 \pmod{9}, so the product must be congruent to 2 \cdot 1 = 2. The digits of the answer add to 1 + 4 + 2 + 2 + 4 + 6 + 0 + 1 = 20, and 20 \equiv 2. The check passes, which finds no error but proves nothing.

(b) Swapping the 4 and 6 leaves the digit sum at 20, so 14{,}226{,}401 passes as well. The two numbers differ by 1{,}800 = 9 \cdot 200, the multiple of 9 the procedure predicts: 9 \cdot (6 - 4) \cdot 100.

(c) Modulo 11, A(4{,}817) = 7 - 1 + 8 - 4 = 10 \equiv -1 and A(2{,}953) = 3 - 5 + 9 - 2 = 5, so the product is congruent to -5 \equiv 6. Then A(14{,}224{,}601) is 1 - 0 + 6 - 4 + 2 - 2 + 4 - 1 = 6 and agrees, while A(14{,}226{,}401) is 1 - 0 + 4 - 6 + 2 - 2 + 4 - 1 = 2 and does not. So 14{,}226{,}401 \ne 4{,}817 \cdot 2{,}953. Multiplying out confirms 4{,}817 \cdot 2{,}953 = 14{,}224{,}601.

Example 7

The same tests in base eight

Find the remainders of (3527)_8 on division by 7 and by 9 without converting it, then check by converting.

Solution

Since 8 \equiv 1 \pmod{7} and 8 \equiv -1 \pmod{9}, Theorems 1 and 2 run with 8 in place of 10. Modulo 7 the number is congruent to its digit sum 3 + 5 + 2 + 7 = 17 = 2 \cdot 7 + 3, remainder 3. Modulo 9 it is congruent to its alternating digit sum, signed from the right, 7 - 2 + 5 - 3 = 7, remainder 7.

Check: (3527)_8 = 3 \cdot 512 + 5 \cdot 64 + 2 \cdot 8 + 7 = 1{,}879, and 1{,}879 = 7 \cdot 268 + 3 = 9 \cdot 208 + 7.

Boundaries

The digit-sum test is for divisors of 9 only. It rests on 10 \equiv 1, which holds modulo m only when m \mid 9. For 6 it fails: S(15) = 6, yet 6 \nmid 15.
Signs and blocks are counted from the right. The ones digit, or the last block, carries the plus sign. Signing from the left flips the sum when the count is even: divisibility survives, but a nonzero remainder r becomes m - r.
A sum is a congruent number, not yet the remainder. S(n) may exceed 8, and A(n) or an alternating block sum may be negative; the remainder is found from it with the division algorithm, 0 \le r < m.
Casting out nines is one-way. A disagreement proves an answer wrong; an agreement proves nothing, and every error that changes the answer by a multiple of 9 (a swapped pair of digits, a 0 written for a 9) goes unseen.

Where this goes next

The tests used powers of 10 that happen to be \pm 1. For a modulus such as 7, the powers 10, 10^2, 10^3, \dots cycle through the remainders 3, 2, 6, 4, 5, 1 and return to 1 at 10^6; computing such powers fast is Powers modulo n, and the reason a power of 10 must come back to 1 modulo a prime other than 2 and 5 is Fermat's little theorem.

Exercises

Sums, alternating sums and blocks

Find the remainders of 7{,}316{,}425 on division by 9 and by 3.
Find the remainder of 73{,}950{,}814 on division by 11.
Use three-digit blocks to find the remainders of 4{,}071{,}532 on division by 7, 11 and 13.
Find the remainder of 2{,}480{,}159 on division by 13.
Use 999 = 27 \cdot 37 to find the remainder of 5{,}206{,}341 on division by 37.
Find the remainders of 3{,}604{,}817 on division by 99 and by 101.

Missing digits

Find every digit d for which (5\,2\,d\,8\,1\,7\,4)_{10} is divisible by 9.
Find every digit d for which (3\,d\,6\,1\,5\,4)_{10} is divisible by 11.
Find every pair of digits a, b for which (4\,a\,7\,3\,b)_{10} is divisible by 8 and by 9.

Casting out nines and elevens

Use casting out nines to show that 6{,}284 \cdot 3{,}719 \ne 23{,}380{,}196.
Use casting out nines to show that 48{,}736 + 29{,}587 \ne 77{,}323, after explaining why the check works for sums.
Show that 22{,}614{,}794 passes casting out nines as a value of 5{,}167 \cdot 4{,}382 but fails casting out elevens.

Other bases

Find the remainders of (3425)_6 on division by 5 and by 7 without converting, then check.
Find the remainders of (\mathrm{2B9E})_{16} on division by 15, 3, 5 and 17 without converting, then check.

Reasoning

Prove that if the digits of a positive integer are rearranged in any order, the difference of the two numbers is a multiple of 9.
Prove that swapping two adjacent, unequal digits of a positive integer changes its remainder on division by 11. Conclude that casting out elevens catches every such swap in an answer.
Prove that every positive integer whose base-ten numeral is a palindrome with an even number of digits is divisible by 11.
Prove that every six-digit number of the form (a\,b\,c\,a\,b\,c)_{10} is divisible by 7, 11 and 13.
Show that 2{,}799 has digit sum divisible by 27 but is not divisible by 27. Explain why Theorem 1’s proof does not carry over to 27, and why three-digit block sums do work modulo 27.
Prove that a positive integer is divisible by 3 exactly when the alternating sum of its binary digits is divisible by 3.
Repeatedly replace a positive integer by its digit sum until one digit is left. Prove that the digit reached is n \bmod 9, except that it is 9 when 9 \mid n.

Answers

1 and 1. S = 7 + 3 + 1 + 6 + 4 + 2 + 5 = 28 and 28 \equiv 2 + 8 = 10 \equiv 1 \pmod{9}; also 1 \bmod 3 = 1.
3. A = 4 - 1 + 8 - 0 + 5 - 9 + 3 - 7 = 3.
3, 3 and 10. 532 - 71 + 4 = 465, and 465 = 7 \cdot 66 + 3 = 11 \cdot 42 + 3 = 13 \cdot 35 + 10.
6. 159 - 480 + 2 = -319, and -319 = 13 \cdot (-25) + 6.
34. 1000 \equiv 1 \pmod{37} since 37 \mid 999, so the number is congruent to 341 + 206 + 5 = 552 = 37 \cdot 14 + 34.
29 and 26. 17 + 48 + 60 + 3 = 128 = 99 + 29; 17 - 48 + 60 - 3 = 26.
d = 0 or d = 9. S = 27 + d, a multiple of 9 exactly when 9 \mid d.
d = 9. A = 4 - 5 + 1 - 6 + d - 3 = d - 9, which lies between -9 and 0, so it is a multiple of 11 only for d = 9: 396{,}154 = 11 \cdot 36{,}014.
a = 7, b = 6. By the last-three-digits test, 8 \mid (73b)_{10}; among 730, \dots, 739 only 736 = 8 \cdot 92 works. Then S = 4 + a + 7 + 3 + 6 = 20 + a must be a multiple of 9, so a = 7: 47{,}736.
S(6{,}284) = 20 \equiv 2 and S(3{,}719) = 20 \equiv 2, so the product is congruent to 4; but S(23{,}380{,}196) = 32 \equiv 5 \pmod{9}.
If a + b = c then S(c) \equiv c = a + b \equiv S(a) + S(b) by the addition rule. Here S(48{,}736) = 28 \equiv 1 and S(29{,}587) = 31 \equiv 4, so the sum is congruent to 5, while S(77{,}323) = 22 \equiv 4 \pmod{9}. (The sum is 78{,}323.)
Nines: S(5{,}167) = 19 \equiv 1, S(4{,}382) = 17 \equiv 8, product 8; S(22{,}614{,}794) = 35 \equiv 8, a pass. Elevens: A(5{,}167) = -3 \equiv 8, A(4{,}382) = -7 \equiv 4, product 32 \equiv 10; A(22{,}614{,}794) = -7 \equiv 4, a fail. (The product is 22{,}641{,}794.)
4 and 4. 6 \equiv 1 \pmod{5}: digit sum 14 \equiv 4. 6 \equiv -1 \pmod{7}: 5 - 2 + 4 - 3 = 4. Check: (3425)_6 = 809 = 5 \cdot 161 + 4 = 7 \cdot 115 + 4.
6, 0, 1 and 14. 16 \equiv 1 \pmod{15}, so the number is congruent to 2 + 11 + 9 + 14 = 36 \equiv 6 \pmod{15}; then 6 \bmod 3 = 0 and 6 \bmod 5 = 1, since 3 and 5 divide 15. 16 \equiv -1 \pmod{17}: 14 - 9 + 11 - 2 = 14. Check: the number is 11{,}166 = 15 \cdot 744 + 6 = 17 \cdot 656 + 14.
Proof. Let m be a rearrangement of n. The two have the same digits, so S(m) = S(n). By Theorem 1, n - m \equiv S(n) - S(m) = 0 \pmod{9}. \square
Proof. Swapping d_{i+1} and d_i changes the number by 9 (d_i - d_{i+1}) 10^i, as in the procedure. Modulo 11, 9 \equiv -2 and 10^i \equiv \pm 1, so the change is congruent to \pm 2 (d_i - d_{i+1}). Since 0 < |d_i - d_{i+1}| \le 9, the number 2 (d_i - d_{i+1}) is nonzero, between -18 and 18, and even, so it is not a multiple of 11. The remainder changes. So a correct product with one such swap fails casting out elevens. \square
Proof. Let the numeral have 2t digits, d_i = d_{2t - 1 - i}. Each pair of positions i and 2t - 1 - i has one even and one odd index, since their sum 2t - 1 is odd, and the two digits are equal. In A(n) the pair contributes d_i - d_i = 0, so A(n) = 0 and 11 \mid n by Theorem 2. \square
Proof. Let x = (abc)_{10}. Then (a\,b\,c\,a\,b\,c)_{10} = 1000x + x = 1001x, and 1001 = 7 \cdot 11 \cdot 13. \square (By Theorem 3 too: the alternating block sum is 0.)
S(2{,}799) = 27, but 2{,}799 = 27 \cdot 103 + 18. The proof needs 10 \equiv 1 \pmod{27}, which is false since 27 \nmid 9. But 27 \mid 999, so 1000 \equiv 1 \pmod{27} and Theorem 3 applies: 799 + 2 = 801 \equiv 18, the true remainder.
Proof. In base two, 2 \equiv -1 \pmod{3}, so 2^i \equiv (-1)^i and n = \sum d_i 2^i \equiv \sum (-1)^i d_i \pmod{3} by the replacement rule. Congruent numbers are divisible by 3 together. \square
Proof. If n has k + 1 \ge 2 digits then n - S(n) = \sum d_i (10^i - 1) \ge d_k (10^k - 1) > 0, since d_k \ge 1, so the process strictly decreases and stops at a single digit r between 1 and 9; it is never 0, because a positive number has a nonzero digit. Each step keeps the remainder modulo 9 by Theorem 1, so r \equiv n \pmod{9}. If 9 \nmid n, then r is in \{1, \dots, 8\} and is n \bmod 9; if 9 \mid n, the only digit from 1 to 9 congruent to 0 is 9. \square