Sunday, May 11, 2008

Is that divisible by 11?

So here's why I decided to do this today: I figured out something that I think is pretty cool. I'm not going to claim that I'm the first- I would be stunned if no one else had spotted this pattern. But I did figure it out for myself, and that's the fun part of solving any puzzle.

First the back story. You probably know that if you sum the digits of a number (eg 4653 sums to 18) and the result is a multiple of nine, then the original number is also a multiple of nine (so 4653 is a multiple of nine, or you could say the same thing a different way, that 4653 is evenly divisible by nine) But have you ever considered why that's so?

It's a fairly straight-forward result of the number system we use, base 10. We can subtract out multiples of 9 without affecting whether 4653 is divisible by 9. I'm not too sure how explict to be here, but if 4653 is divisible by 9, then 4653 - 9 is too. So is 4653 -18, and 4653-99. We can represent the number 4653 as (4 X 1000 + 6 X 100 + 5 X 10 + 3.) Then we can subtract out 4 X 999, 6 X 99, and 5 X 9. This leaves us with 4 + 6 + 5 + 3, but we haven't changed whether the number is divisible by 9. We can sum those digits together, and if the result is divisible by 9, so was the original number. This trick also works with 3, for the same reason. As we subtract out our multiples of 9, we are of course also subtracting out multiples of 3. If the original number was a multiple of 3, subtracting out 3's, no matter how many times, won't change that fact.

Okay, that I figured out sometime in high school. Here's an exciting but probably pretty meaningless thing I figured out recently: The same logic will hold true for all number base systems. The number one less than the base- the last single digit- will do this same trick in any base. So in base 8, you can determine whether a number is divisible by 7 by summing the digits. If the result is a multiple of seven, so was the original. So 151 (base 8) sums to 7, and is thus divisible by 7. Let's check: 151 (base 8)= 64 + 5 X 8 + 1 = 105. 105 is 15 X 7.

Let's take an example in base 11: 2355. This sums to 15, so it's not divisible by 10. However just as 3 works in base 10 because it's a factor of 9, so will 5 work in base 11, because 5 is a factor of 10. 2 will also work for the same reason. So we can say before bringing it back to our native system to check (and I haven't checked as I write this) that 2355 (base 11) is divisible by 5, but not 2 or 10. 2355(b11) = 2 X 1331 + 3 X 121 + 5 X 11 + 5 or 2662+363+55+5= 3085(b10). Divisible by 5, but not 2 or 10! Excellent, huh?

Just one more: in base 13, the sum-the-digits trick would work for 2, 3, 4, 6 and 12!

However, as I pointed out, I don't know that this is of any use; I never do math in any base but 10. Buuuuuuuut....

As I was waking up this morning (that is, not thinking too clearly yet, trying desperately to ignore the yammering heads on CNN) I got confused thinking about 11 divisiblity in base 10. I mean, 99 is also a multiple of 11 right? So why doesn't sum-the-digits work for 11?

This state of mind where something seems like it ought to be so, but it clearly isn't, is unsettling for me. It's almost always a bad assumption (as it is here), but I am definitely compelled to figure it out asap. So long story short, 99 is a multiple of 11, but 9 and 999 are not. C'est la vie. But wait a minute... 9999 and 999999 are. And so are 11, 1001 (990 + 11), 100001 (99990 +11). In other words for even powers of 10, one less is a multiple of 11. For odd powers of 10 one more is a multiple of 11. So how about add, subtract, add, subtract, rather than just add? It seems to work. Take 3,376,505 and start from the right (the ones digit): add the 5, subtract the 0, add the 5, subtract the 6, add the 7, subtract the 3 and add the 3, for a total of 11. So 3376505 is divisiible by 11. In this case the total being "divisible by 11" would include negative multiples (e.g. -22) and zero.

I love these kinds of little tricks and have been consciously accumulating them for years, but I've never had one to easily determine divisibility by 11 before. Again, I'm not claiming to be the first to figure this out; I would be surprised if this hadn't been discovered roughly the same time people started using modern numerals (as opposed to Roman numerals- I don't know how they figured out anything beyond adding with that system). Still, it's a trick I'm glad to have, and I'm pretty pleased with myself for findng it.

One last comment: I'm not as confident in my logic with the "11 trick" as I am with the "base minus one trick." I would be tickled if a real mathematician could confirm that this actually does work as I've advertised. It's worked for all the examples I've tested but you can't really verify by brute force in math. I'm also curious, but haven't sat down to work it out, if this specific instance is also generalizable across different bases.

Disclaimer: The author of this blog is not a professional mathematician- barely an amateur. Nevertheless he feels the dangers in these sorts of activities, while not inconsequential, are low enough to recommend trying them at home. Even without parental supervision.


Matty Boy said...

Howdy. The alternating sum trick for divisibility by 11(base n) will work in any number base. In terms of number theory, it relies on the fact that (-1)^2 = 1. Nice work.

Best of luck with the blog. It can be a lot of fun.

Batman said...

Lockwood, in case you forget the proof I showed you just represent your number by a linear combination and multiply it by that base's 11: (a0*B^0+a1*B^1+...+an*B^n)(B^0+B^1) and then after you group all the terms by their common B value replace all the B's with -1 and then your sum should be zero.