First, a few words on modular arithmetic. I really wanted to avoid talking about modular arithmetic, but I tried writing this post without it, and it became overly complicated and I used the word remainder, and remainders of remainders, about eleventy trillion times. So here it is. Modular arithmetic is basically shuffling around integer multiples of things. We say that two numbers A and B are ‘congruent mod k’, if A = n*k + B for some integer n. So, for example, 17 and 7 are congruent mod 10 since 17 = 10*1 + 7. 107 is also congruent to 7. -3 is also congruent to 7, since 7 = 10*1 + -3. Notice the link to division and remainders. 107 gives a remainder of 7 when divided by 10 and is congruent to 7 mod 10, because in each case you’re subtracting the largest possible multiple of 10 from 107. When two things differ by an integer multiple of k, they are congruent mod k. We can think of divisibility then as when a number N is congruent to 0 mod k. 100 is congruent to 0, since 100 = 10*10 + 0, 100 gives a remainder of 0, 100 is divisible by 0, it’s all saying the same thing.
There are a small set of rules people can use to determine whether an integer is divisible by numbers like 2, 3, 4, 5, 6, 8, 9, 10, etc. Rarely does anyone go much beyond this, or even address the lonely 7. For the most part, these rules are simply shortcuts for calculating congruences. Congruencies? For example, we know that any number N can be written in the form N = 10*A + B, where B is the last digit of the number, and A is the rest of the digits. We can also say then, N = 5*(2*A) + B. Notice that B Thus, N is congruent to B mod 5. If N is divisible by 5, it is congruent to 0 mod 5, so we want B to be congruent to 0 mod 5. The only values from 0 to 9 (since B is a single digit) that are congruent to 0 mod 5 are 0 and 5. Thus, N is only congruent to 0 (and thus divisible by 5) if it’s last digit is a 0 or a 5.
All the other divisibility rules accomplish the same thing, finding a shorter way to calculate these congruences with the divisor. Dividing by 3, it turns out that N is congruent to, and thus leaves the same remainder as, the sum of the digits of N.
But there’s a way at getting into the problem indirectly, sort of sideways. Calculating whether or not a number is congruent to 0 mod the divisor without actually calculating the remainder.
In brief, start with your number N, (7931, for example). Take the last digit, double it, and subtract it from the remaining digits. 793 - 2*1 = 791. Repeat. 79 - 2*1 = 77. Eventually you will get to a number that is obviously divisible by 7, or obviously not. If you reach a number divisible by 7, the original number is as well. We reached 77, 7*11, so 7931 is divisible by 7. And if you check it is. This is very fast, as you effectively lose a digit with each step ^^
Below, I explain why this works, and extend the same trick to derive simple divisibility tests for 11, 13, 17, and 19.
(more…)