Everyone's heard of the trick for finding out if a number is divisible by 9. Just add up all the digits, and if the result is divisible by 9, then the original number is divisible by 9 as well. Another trick for finding if a number is divisible by 11 is to add, and then subtract alternatively each digit of the number, and if the result is divisible by 11, then the original number is divisible by 11.
These tricks (as well as others) can be explained pretty easily with modular arithmetic. Modular arithmetic is another way of thinking about numbers that places all the integers into what are called equivalence classes. For example, when considering the integers modulo 9, there are 9 equivalence classes, let's call them 0, 1, 2, 3, 4, 5, 6, 7 and 8. And a number is placed into the equivalence class given by the remainder when you divide by 9. So the numbers in the 0 equivalence class are 0, 9, 18, 27, 36, etc (as well as -9, -18, -27, etc), and the numbers in the 1 equivalence class are 1, 10, 19, 28, -8, -17, etc. An interesting consequence is if you pick 2 classes, A and B, then regardless of the elements you choose from those classes, when you add them, the result is always in the same equivalence class, namely A + B mod 9. Similarly when you multiply any 2 elements from those classes, the result is always in the same equivalence class, namely A * B mod 9.
Okay, now we get back to the divisibility tricks. For the divisible-by-9 trick, let's look at the numbers modulo 9 (or mod 9 for short). Notice that 1, 10, 100, 1000 and all positive integer powers of 10 fall into the same equivalence class, namely the 1 class. Given a number
and modulo 9, this is
And so a number is in the same class modulo 9 as the sum of its digits.
The divisible-by-11 rule follows from the fact that the numbers 1, 100, 10000, etc are all in the 1 mod 11 class, and the numbers 10, 1000, 100000, etc are all in the 10 mod 11 class. The 10 mod 11 class also has -1, so the number can be written
Here's a list of tricks for finding if a number is divisible by the numbers 2 through 15. All they actually do is tell you how to get another number in the same equivalence class that tends to be much smaller, so that it's easier to tell if it's in the 0 equivalence class (meaning that it's divisible).
2 : Just take the ones digit (if the ones digit is divisible by 2, then the whole number is divisible by 2)
3 : Add all the digits. If the result is divisible by 3, then the original number was also.
4 : The ones digit plus two times the tens digit.
5 : The ones digit by itself
6 : The ones digit minus two times the sum of the rest of the digits
7 : The ones digit, plus three times the tens, plus two times the hundreds, minus the thousands, minus three times the ten-thousands, minus two times the hundred-thousands, plus the millions, etc (the pattern is 1, 3, 2, -1, -3, -2, repeat). This is because
8 : The ones digit plus two times the tens digit plus four times the hundreds digit
9 : Add all of the digits
10 : The ones digit by itself
11 : The ones digit, minus the tens digit, plus the hundreds digit, minus the thousands digit, etc
12 : The ones digit, minus two times the tens digit, plus four times the sum of the rest of the digits
13 : The ones digit, minus three times the tens, minus four times the hundreds, minus the thousands, plus three times the ten-thousands, plus four times the hundred-thousands, etc (the pattern is 1, -3, -4, -1, 3, 4, repeat)
14 : The pattern is 1, -4, 2, 6, 4, -2, -6, then go to -4 and repeat
15 : The ones digit, minus 5 times the sum of the rest of the digits
I'll leave it at that. I'm sure its obvious enough how to create these tricks by now (and they're getting a little too complicated anyway).
No comments:
Post a Comment