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.
Very important in this is the decomposition of numbers into the form N = 10*A + B, where B is the last digit of N, and A is all previous digits. 7931 = 793*10 + 1. The divisibility test for 7 then amounts to instead of dividing 10*A + B, you divide A – 2*B, which is of course a much smaller number.
So, we have this number N = 10*A + B. Consider 5*N. Notice that if N is divisible by 7, 5*N will also be divisible by 7. But and if 5*N is divisible by 7, N must be divisible by 7, since 5 and 7 are prime.
Thus we have
What’s neat is when we start grouping 7’s, like so.
And there it is. 5*N is congruent to A – 2*B. Thus, if A – 2*B is congruent to 0 mod 7, so is 5*N, and thus so is N. Notice that 5*N isn’t necessarily congruent to N mod 7, unless of course they are both congruent to 0.
And we can repeat as necessary, since we’ve reduced the original problem to a smaller version of the same problem. If A – 2*B is still too large to tell if it’s divisible by 7, we simply apply the same rule, and at each step the result is only congruent to 0 if the original number was congruent to 0.
It’s very slick. In essence, it’s as though dividing 5*N by 7 is easier than dividing N by 7. Backing into the problem, sideways.
We can use this same trick to develop divisibility rules for 11, 13, 17 and 19. Really we could do it for far more than that, but ultimately who wants to. You can only ever remember so many divisibility rules, anyway.
We’ll start with 11. We begin in the same way, with N = 10*A + B, B being the last digit of N, and we want to find something to multiply N by so that the coefficients on A and B became nicely reducible mod 11.
So, for 11, consider 10*N. Notice again, 10*N is divisible by 11 if and only if N is divisible by 11.
So 10*N is congruent to A – B mod 11. Thus the divisibility rule for 11 is take your number, and subtract the last digit from the rest of the digits. Repeat until you get something that is obviously divisible by 11 or obviously isn’t – whichever it is, the starting number was as well.
As an example, consider 10813. 1081 – 3 = 1078. 107 – 8 = 99. 99 is obviously divisible by 11, so 10813 is as well. Consider then 10814, which is obviously not divisible by 11. 1081 – 4 = 1077. 107 – 7 = 100. 10 – 0 = 10. 10 is not divisible by 11, so neither is 10814.
And on to 13.
Notice that in both cases, 7 and 11, the final expression in A and B had just a single A, with a coefficient of 1. This is very handy for mental math, because A can be quite long and it would be a pain to have to multiply it by something. So what we should aim for is to always have a coefficient of 1 on A.
So, in choosing a number k to multiply N by, we want 10*k to be congruent to 1 mod 13. Notice that 40 = 3*13 + 1, so 40 is congruent to 1 mod 13. So let’s consider 4*N. Notice again that 4*N is only divisible by 13 if N is.
So, 4*N is congruent to A + 4*B. Thus, the divisibility rule for 13 is take your number and add four times the last digit to the rest of the digits. Repeat until the result is small enough. If it is divisible by 13, then the original number was as well.
Notice that in the interesting case of 26, 2 + 4*6 = 26. But it’s pretty clear that 26 is divisible by 13. But it does make me wonder about other special cases. In other words, when does 10*A + B = A + 4*B? Simplifying, we get that 9*A = 3*B, or 3*A = B. Remembering that B is between 0 and 9, this gives solution pairs (A, B) of (0,0), (1, 3), (2,6), (3,9). And in each of those, the number itself (0, 13, 26, 39) are all divisible by 13. So … no special cases to really worry over.
However, this post has gone on long enough, so unless there are any questions, I will leave it to you intrepid reader to work out the rules for 17 and 19. And if you’re interested, Wikipedia has a nice list of other divisibility rules, though curiously 11, 17 and 19 seem to be overlooked. Hmm.
That’s really neat. I hadn’t thought about it that way before. I was thinking about which of these “divisibility rules” are quirks of our base 10 counting system. But the way you explained it seems to suggest that with suitable adjustments, you could build divisibility rules for any base number. Right?
Comment by Seamus — July 16, 2008 @ 12:42 pm
Oh certainly. For example, in base 16, you’re really more interested in the decomposition N = 16*A + B.
Consider then for 7, that 4*N = 64*A + 4*B = 63*A + A + 4*B = 7*(9*A) + A + 4*B.
So 4*N is congruent to A + 4*B, and you can use that for your divisibility rule in base 16.
Another thing that’s interesting me is that you can technically use this technique to build similar divisibility rules for any prime number. For example, if you have N = 10*A + B, the divisibility rule for 41 is to look at A – 4*B. Which is surprisingly simple, I think.
But these difficulty of using these divisibility rules depends on the coefficient on B. So what divisors yield the worst case divisibility rules?
You’d essentially, following the map I laid out in the post, want to solve 10*X === 1 (mod p) for the prime p that yielded the maximum possible value for X (mod p).
Something to think about when I finished this other blasted work v.v
Comment by Fox — July 16, 2008 @ 4:02 pm
You apply the 11 rule in a way that’s a little overly complicated, as simple as it seems. N will be divisible by 11 if and only if the alternating sum of the digits is. For instance 10813 is a multiple of 11 since 1-0+8-1+3=11 is.
Also note that by similar argumant your rule for divisibility by 3 also works for 3^2=9, but no higher powers of 3 (in base 10 at least).
Comment by thetwentyeighthline — July 17, 2008 @ 9:28 am
I was thinking about your work here — fascinating, and very well done, by the way — and it occurred to me that you could create a generating formula for any prime divisibility rule in the following way (note that the choice of coefficient on the B isn’t automatic, but that many choices might work, and you can pick the one that’s easiest for you to work with). Now, this might well be what you were getting at with the post, but I tried to do it constructively and generally, and here’s what I got:
Say, given integeres A and B, 0<=B<=9, a prime p divides N = 10A+B. Then, for some integer k, 10A+B = pk.
Now, solve for B, to get: B = pk – 10A.
Next, multiply through by some arbitrary constant c (not yet necessarily an integer) to get: cB = pck – 10cA
Add in another A to get: A + cB = pck + (1-10c)A
Now, this will be divisible by p when both terms on the right hand side are. The first term is, and we can then pick c to force the second term to be as well:
1 – 10c = pk’, some integer k’. Rearranging gives: c = (pk’ + 1)/10
Now, for a given prime number p, we can find the k’ which givees a convenient integer c, and can then use it to check divisibility using your cool inductive method.
For instance, if p = 7, we can choose k’ = -3, which gives c = -2, and we have the A-2B of your awesome post.
Similarly, p = 11 naturally leads to k’ = -1, and c = -1, as you discussed; p = 13, k’ = 3, c = 4.
The only downside here is that the formula, at least as I’ve worked it out in a few minutes here, doesn’t generate the k’ itself; it takes a little trial and error to find it (though ultimately I suppose we’re lloking for k’ such that pk’ is congruent to 9 mod 10, and there’s probably someone slicker than I who can do more with that).
(Here’s some more: p=17, k’=-3, c=-5; p=19, k’=1, c=2; p=23, k’=3, c=7; p=31, k’=-1, c=-3. Enjoy finding others!)
PS: I ‘m entirely confident that this is work that’s been done a bazillion times before. I don’t think this is anything new, but it is pretty fun…
Comment by Kevin — July 24, 2008 @ 1:58 am
It don’t have my answer!!:[
Comment by ..ms.86 — September 14, 2008 @ 2:24 pm