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^(k1) + ... + 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^(k1) + ... + 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[k1]*10^(k1) + ... + 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 lefthand 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 lefthand side).
How can we write this?
10^(2k+1) + 1 = 11*(1 + Sum[i=0 to k1]{9*10^(2i+1)} )
10^(2k)  1 = 11*( Sum[i=0 to k1]{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*k1]*10^(2*k1) + ... + d[1]*10 + d[0]
= d[2*k]*(11*b[2*k] + 1) + d[2*k1]*(11*b[2*k1]  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*k1] + ...  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*k1] + ...  d[1] + d[0] =
(d[0] + d[2] + ... + d[2*k])  (d[1] + d[3] + ... + d[2*k1]),
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 threedigit 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 3digit 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 threedigit groups works here, too.
Numbers divisible by 17
This is harder. You would have to use alternating sums of 8digit 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 threedigit
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 fivedigit
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 fourdigit
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 twodigit groups
together with alternating signs. The sum is divisible by 101 if and
only if the original number is.
On to Alternate Test Method
Back to Rules for 10,2,4,8,2^k,5,25
