Numbers divisible by 3

Numerals whose sum of digits is divisible by 3 represent numbers divisible by 3:

This one is different, because 3 does not divide any power of 10 evenly. That means we will have to consider the effect of all the digits. Here we use this fact:

    10^k - 1 = (10 - 1)*(10^(k-1) + ... + 10^2 + 10 + 1)

This is a fancy way of saying 9999...999 = 9*1111...111. So that our notation doesn't get way out of hand, let's make a definition:

    10^k = 9*(10^(k-1) + ... + 10^2 + 10 + 1) + 1
         = 9*a[k] + 1

We use this to rewrite our powers of 10 as 10^k = 9*a[k] + 1.

Now if we let the digits of the number be d[0], d[1], d[2], and so on, the polynomial form of a numeral looks like this:

    d[k]*10^k + d[k-1]*10^(k-1) + ... + d[1]*10 + d[0]
    = d[k]*(9*a[k] + 1) + ... + d[1]*(9*a[1] + 1) + d[0]
    = 9*(d[k]*a[k] + ... + d[1]*a[1]) + d[k] + ... + d[1] + d[0]

Now notice that 3 divides the first part, so the whole number is divisible by 3 if and only if the sum of the digits is.

It is worth noting that once we have computed the sum of the digits to test for divisibility by three, we can apply the same test to this number to see if it is divisible by three! For example, 5697459746754985794849 is divisible by 3 if and only if 5+6+9+7+4+5+9+7+4+6+7+5+4+9+8+5+7+9+4+8+4+9 = 141 is, if and only if 1+4+1 = 6 is. Since 6 is a multiple of 3, so is 141, and so is 5697459746754985794849. This kind of repeated application of the test is known as testing recursively.

  Numbers divisible by 9

Numerals whose sum of digits is divisible by 9 represent numbers divisible by 9:

Use the same equation as the previous case. Since 9 divides the first part, the whole number is divisible by 9 if and only if the sum of the digits is.

This test may also be applied recursively.

  Numbers divisible by 11

Numerals whose alternating sum of digits is divisible by 11 represent numbers divisible by 11:

Here the phrase "alternating sum" means we alternate the signs from positive to negative to positive to negative, and so on. We use this fact: 10 to an odd power plus 1 is divisible by 11, and 10 to an even power minus 1 is divisible by 11.

An example of the first statement is 10000...0001 = 11*9090...9091 (where there are an even number of 0's on the left-hand side), and an example of the second statement is 99999...9999 = 11*9090...0909 (where there are an even number of 9's on the left-hand side).

How can we write this?

    10^(2k+1) + 1 = 11*(1 + Sum[i=0 to k-1]{9*10^(2i+1)} )
    10^(2k) - 1 = 11*( Sum[i=0 to k-1]{9*10^(2i)} )

To get rid of some of that ugliness, we give it a name and use that name from here on out, so define b[x] appropriately to make the following two equations work:

    10^(2*k+1) = 11*b[2*k+1] - 1, and
    10^(2*k) = 11*b[2*k] + 1.

Here k is any nonnegative integer. We substitute that into the polynomial form, so:

    d[2*k]*10^(2*k) + d[2*k-1]*10^(2*k-1) + ... + d[1]*10 + d[0]
    = d[2*k]*(11*b[2*k] + 1) + d[2*k-1]*(11*b[2*k-1] - 1) + d[1]*(11*a[1] - 1) + d[0]
    = 11*(d[2*k]*b[2*k] + ... + d[1]*a[1]) + d[2*k] - d[2*k-1] + ... - d[1] + d[0]

The first part is divisible by 11 no matter what the digits are, so the whole number is divisible by 11 if and only if the last part, which is the alternating sum of the digits, is divisible by 11. If you prefer, you can write

    d[2*k] - d[2*k-1] + ... - d[1] + d[0] =
    (d[0] + d[2] + ... + d[2*k]) - (d[1] + d[3] + ... + d[2*k-1]),

so that you add up every other digit, starting from the units digit, and then add up the remaining digits, and subtract the two sums. This will compute the same result as the alternating sum of the digits.

This test can also be applied recursively, once we realize that we can discard any negative signs which might occur. This is because whenever a negative number has a divisor, its absolute value has the same divisor.

  Numbers divisible by 7

There is a trick for 7 which is not as well known as the others. It makes use of the fact that 10^(6*k) - 1 is divisible by 7, and 10^(6*k - 3) + 1 is divisible by 7. It goes like this:

Mark off the digits in groups of threes, just as you do when you put commas in large numbers. Starting from the right, compute the alternating sum of the groups as three-digit numbers. If the result is negative, ignore the sign. If the result is greater than 1000, do the same thing to the resulting number until you have a result between 0 and 1000 inclusive. That 3-digit number is divisible by 7 if and only if the original number is too.

Example:

    123471023473 = 123,471,023,473, so make the sum
    473 - 23 + 471 - 123 = 450 + 348 = 798.
    798 = 7*114, so 798 is divisible by 7, and 123471023472 is, too.

An extra trick is to replace every digit of 7 by a 0, every 8 by a 1, and every 9 by a 2, before, during, or after the sum, and the fact remains. The sum could also have been computed as

        473 - 23 + 471 - 123
    --> 403 - 23 + 401 - 123 = 380 + 278
    --> 310 + 201 = 511 = 7*73.

This "casting out 7's" part works because 7 always divides 7*10^k for any nonnegative integer k. If you like that trick, you may also like the "general casting out" principle on the next page.

This test may also be applied recursively.

  Numbers divisible by 13

The same trick that works for 7 works for 13; that is, 13 divides 10^(6*k) - 1 and 10^(6*k - 3) + 1, so the alternating sum of three-digit groups works here, too.

  Numbers divisible by 17

This is harder. You would have to use alternating sums of 8-digit groups!

  Numbers divisible by 27 and 37

We use the fact that 27*37 = 999 = 10^3 - 1. Mark off the number in groups of three digits starting from the right, and add the three-digit groups together. The sum is divisible by 27 or 37 if and only if the original number is.

  Numbers divisible by 41 and 271

We use the fact that 41*271*9 = 99999 = 10^5 - 1. Mark off the number in groups of five digits starting from the right, and add the five-digit groups together. The sum is divisible by 41 or 271 if and only if the original number is.

  Numbers divisible by 73 and 137

We use the fact that 73*137 = 10001 = 10^4 + 1. Mark off the number in groups of four digits starting from the right, and add the four-digit groups together with alternating signs. The sum is divisible by 73 or 137 if and only if the original number is.

  Numbers divisible by 101

We use the fact that 101 = 10^2 + 1. Mark off the number in groups of two digits starting from the right, and add the two-digit groups together with alternating signs. The sum is divisible by 101 if and only if the original number is.