♬ A Lowly Fan's Notes on Notes ♬: August 2022

Tests for divisibility by digits:

First, let's dispose of the easy digits: If divisible by 10, the final digit is always 0.

If divisible by 5, the final digit is always 0 or 5. Note that an even number times 5 is 2nx5 = 10n, so that the last digit is always 0; an odd number times 5 is (2n+1)x5 = 10n + 5, so that the last digit is always 5.

If divisible by 2, the last digit is 0,2,4,6 or 8. If divisible by 4, the last two digits are divisible by 2 twice, as in 80/2=40; 40/2=20. So 60480 is divisible by 4 (yielding 15102). Similarly, if a number is divisible by 8, the last three digits are thrice divisible by 2. We have already divided 60480 by 4 and can see that 15102 is divisible by 2, giving 7551. So 60480 is divisible by 8.

By glancing at 60480, we know it is divisible by 10, 2, and 5. We need do only a tad more to test for other digit divisors.

Divisibility by 9

Is 60480 divisible by 9?

We add the digits and get 18. We can do that again (not really necessary) and we'll get 9. If the digit sum is divisible by 9 then the entire number is divisible by 9. In fact, 9x6720 = 60480.

Divisibility by 3

Clearly if a number divides by 9, then it divides by 3. But the converse does not hold. Yet, if a number divides by 3, then its digit sum divides by 3. But we cannot necessarily add that sum and keep going until we obtain a 3, as in the case of division by 9. Consider 3669. 3+6+6+9 = 24, which is divisible by 3. But 2+4 = 6, which though divisible by 3, is not 3.

Divisibility by 6

So we can check if a number divides by 6 by testing for 2 and 3.

Divisibility by 7

A curious case is 7. To check 60480 we multiply the last digit by 5 and then add the rest. 5x0 = 0. 0+6048 = 6048. We still are puzzled and so we repeat: 5x8=40. 40+604 = 644. One more time: 4x5=20. 20+64 = 84, which is divisible by 7. But, in case you didn't remember that 7x12=84, we can further repeat: 5X4 = 20. 20+8 = 28, which is 7x4.

Divisibility by 11

In the case of 11, the alternating sum of the digits must add to 0 or some other multiple of 11. Try 60480 and we get 2, and hence we know that 60480 is not divisible by 11. On the other hand 48312 yields 4 - 8 = -4. -4 + 3 = -1. -1 - 1 = -2. -2 + 2 = 0. So 48312 divides by 11.

Proof for 7
In base 10, we may write any number greater than 10 as 10x + y. Well, surely if 10x+y is divisible by 7, then so is 50x + 5y. Regrouping that last, we get 49x + (x + 5y). We needn't worry about 49x, as that plainly divides by 7. So the question is, does x + 5y divide by 7? That, in fact, is our test, which is now proved.

Proof sketch for 9
This approach can also be used for 3. To complete the proof, apply mathematical induction.

Consider a three-digit number in base 10: xyz.

This means 10²x + 10y + z.

The difference between that number and the number's digit sum is:

10²x + 10y + z - (x + y + z) = 99x + 9y = 9(9x + y).

That is, 9(9x + y) + x + y + z = 10²x + 10y + z.

Hence if and only if x + y + z divides by 9 does the original number divide by 9.

Proof for 11
This proof uses modular arithmetic. Since 10ⁿ is congruent to (-1)ⁿ mod 11, we see that 1, 100, 10000, 1000000, etc. have remainders 1 when divided by 11, and 10, 1000, 10000, etc. have remainders (-1) when divided by 11. Thus
2728 = 2 * 1000 + 7 * 100 + 2 * 10 + 8,
so its remainder when divided by 11 is just 2(-1) + 7(1) + 2(-1) + 8(1), the alternating sum of the digits. (It’s sum is the negative of what we found above because the alternation here begins with a -1.) But either way, if this alternating sum is divisible by 11, then so is the original number.

In fact, our observation shows more: that in fact when we take the alternating sum of the digits read from right to left (so that the sign of the units digit is always positive), then we obtain N mod 11.

(This proof from Su, Francis E., et al. “Divisibility by Eleven.” Math Fun Facts.
https://math.hmc.edu/funfacts/divisibility-by-eleven/ .)

Non-modular view of the 11 test
If modular number theory is not your thing, here is a simple demonstration of how the test for a factor of 11 works.

In base 10 (what everyone is used to), a three-digit number abc means a x 10² + b x 10 + c. For example, 931 is 900 + 30 + 1.

So we commonly follow the pattern of multiplying abc x 11, thus:

abc
  11
------
abc
  abc
-------
a + (a+b) + (b+c) + c

So by the alternating sum, we have

a - (a+b) = -b
-b + (b + c) = c
c - c = 0

You can, if you wish, use induction to show that this works when our integer has any number of digits.

But there are times when the sum doesn't go to 0 but goes to 11 (though 11 of course goes to 0, as in 1 - 1).

How so?

Consider 919 x 11.

We follow the hand formula:

919
   11
------
919
919
--------
10109

The alternating sum is 1 - 0 =1, 1+1 = 2, 2-0 = 2, 2+9 = 11.

The sum 11 shows up because of how we carry digits from one column to the next. Yet, note that, by not "carrying," we may also write the sum of 919 + 9190 thus:

9 10 10 9.

Plainly, that alternating sum is 0.

Note that here

9 10 10 9

means

9x10⁴+10 x 10³+10x10²+9,

yielding

10⁴+10²+9.

Adding in the conventional way, we have

10,000
    100
       9
-----------
10109

which matches 11x919.

More examples:

The number 627 = 11x57.

You can check that the digits' alternating sum is 11. The sum 57+570 can be written in our particular notation: 5 12 7. You can check that the alternating sum is 0.

Next we look at 11x177 = 1947. The alternating sum is 1-9=-8; -8+4=-4; -4-7=-11.

This establishes that a -11 can indicate that the integer is divisible by 11.

Yet, we can use our notation to write the integer as 1 8 14 7, where the alternating sum is 0.

Now we look at 81719 = 11x7429.

8-1=7;7+7=14;14-1=13;13+9=22.

This shows that a multiple of 11 can indicate that the integer is divisible by 11.

Using our method to write the integer as 7 11 6 11 9, we have 7-11=-4; -4+6=2; 2-11=-9; -9+9=0.

We can easily see that alternating sums generate many multiples of 11 via the alternation 90909..., which yields 3x9=27. So we attach a 5 to get 909095, or 9-0=9; 9+9=18; 18-0=18; 18+9=27; 27-5=22.

90909093 gives the alternating sum 33 and so is divisible by 11. 9090909091 gives 44. But 90909090909 yields 54 and there is no digit we can subtract to get a multiple of 11. Yet, 8080808080808 yields 56 and so 80808080808081, which yields 55, must be divisible by 11. In fact 80808080808081/11= 7346189164371.

Consider this more or less random number in which the second digit is less than the first, the fourth less than the third, and so on:

6394731.

We have 6-3=3; 3+9=12; 12-4=8; 8+7=15; 15-3=12; 12+1 = 13. So to form an integer that divides by 11, we attach a 2 to the string: 73461891643712. This must divide by 11. And it does:

73461891643712/11= 6678353785792.

Another point:

A symmetrical integer with an even number of digits always divides by 11. You can see this from abba, where a-b+b-a=0.

Consider 7337. The alternating sum is 0. But the symmetrical integer 73037 does not zero out and does not divide by 11.

Note that abcba yields 2(a-b) + c. In the case of 73037 we have 7-3=4; 4+0=4; 4-3=1; 1+7=8 or, that is, 2(7-3)+0 = 8.

Using routine base 10 notation, 11's show up
We can see how it is that the base 10 system can yield 11k for the alternating sum (where k can include -1), by the following:

ab
ab
----------

As our sum has only two rows, the sum for the second column from the right cannot exceed 18. So, if b+c > 9, we write (b+c)-10. The carry digit can only be 1 (or 0 for no carry).

We have for the alternating sum

a+1 -(a+b-10) + b = a + 1 -a -b + 10 + b = 11.

It is possible for an alternating sum to zero out even when there is carrying.

abc
abc
---------

We add traditionally from the right, thus:

c + (b+c)-10 , (a+b+1) - 10, a+1

Then our alternating sum, from the left, is

(a+1) - (a + b +1 - 10) + (b+c+1 -10) - c

or

a+1 - a -b - 1 + 10 + b + c - 10 -c = 0.

But note that this isn't always the case. Suppose we have only the second from the right column as a carry column. Then we have

c, (b+c)-10, (a+b+1), a

The alternating sum is then

a - a - b - 1 + b + c -10 -c = -11

If we make the third column from the right the carry column, we get

c, (b+c), (a + b -10), a+1

and the alternating sum is

a+1 - a - b +10 + b + c - c = 11.