That "Divisible by 11" Rule

Over some tweets about division mental tricks lately I got a question about why the somewhat well known test for eleven works.

If you are not one who grew up BC(before calculators)  working with mental arithmetic, some of these may not be known to you, so here is the one about which they were asking. 
If you take a number, say 31492435 and want to know if it is divisible by eleven, the old-school common trick was to take every other digit and find the sum, then do the same with t he remaining digits.  If these two totals differ by a multiple of eleven, then it is divisible by 11. ( I like a more effective one if you suspect that tests divisibility by 7, 11, and 13 all at once, and  I think is a simpler approach that I will explain after answering the primary question.)

So to begin, I'd like to explain why the more common test of "Casting Out Nines" works.

The secret behind casting out nines is hidden in the following set of equalities:

10 = 1*9+1

100 = 11*9 +1

1000= 111*9+1

10000= 1111*9+1

So if we have a number like 1234, which is 1000+200 + 30 + 4, we can rewrite it as 1(111*9 + 1) + 2(11*9+1) + 3(1*9+1) + 4. Distributing the numbers powers of ten gives me 111*9 + 1+ 22*9+2 + 3*9+3 + 4 collecting all the terms that are multiples of nine gives us 136*9 + 10. Since nine will divide evenly into the 136*9, the remainder is the remainder when ten is divided by nine, and of course we know that 10 = 1*9+1, so the remainder is one.

For elevens the pattern is slightly different. Notice that :

10 = 1*11 –1

100 = 9*11 +1

1000= 91*11-1

10000= 909*11+1

100,000= 9091*11-1

….. and each multiple of ten alternates being one more than or one less than a multiple of 11. So if we expand 1234 as before into 1000+200 + 30 + 4, we can rewrite it as 1(91*11 –1) + 2(9*11+1)+ 3(1*11-1) + 4 . Expanding as before we get some powers of eleven, and the remaining numbers are –1 + 2 – 3 + 4 = 2; so the 1234 divided by 11 leaves a remainder of 2.

It is very similar to the method of casting out nines, except that we alternate adding and subtracting instead of adding all the terms. Most people find it easier to start at the right since the constant term is always added, but you must be able to deal with small negative numbers. For instance if we use 4152, we will do 2 – 5 + 1 – 4 which yields –6. We know there can not be a negative remainder, so what to do. Simply remove this amount from the base, 11, and the answer is revealed. The remainder is 5.

T. Just be aware that if you get a negative number, it means the remainder is the elevens compliment (11-r) of that number. If you just use the sums of the  alternate terms, you don't know the remainder for certain, but it still tests divisibility.

My favorite method that I mentinoed above, uses the idea that 7*11*13 = 1001, so for big numbers, it can be quicker to subtract out multiples of 1001, or 10010, or 100100, etc.

For 4153 you can quickly see by inspection that it is not divisible by 2, 3, or 5. If you reduce it by subtracting 4*1001 = 4004 to get 149. Since 7 goes into that with remainder of two, the original number has a remainder of two on division by 7 also. And since 1+9 - 4 is not zero, or a multiple of eleven then it is not divisible by 11, and a quick mental inspection says that 149 is not divisble by 13 either, so we've eliminated a lot of numbers quickly in testing for primes.