I learned something new today!
Many people probably know of these simple divisibility rules:
- An integer is divisible by 10 if it ends in a zero.
- An integer is divisible by five if it ends in zero or five.
- An integer is divisible by two if its final digit is.
- An integer is divisible by three or nine if the sum of its digits is.
- An integer is divisible by six if it is divisible by both two and three.
Slightly less well-known are these rules:
- An integer is divisible by four if the two-digit number formed from its last two digits is.
- An integer is divisible by eight if the three-digit number formed from its last three digits is.
That last one is simpler than it sounds—you don’t have to memorize all the three-digit numbers that are divisible by eight (that would be rather silly!), since it’s pretty easy to try dividing a three-digit number by two in your head three times. If you can divide it by two three times, it’s divisible by eight; if you hit an odd number before the third division, it’s not. For example, 29873458636 -> 636 -> 318 -> 159, oops, not divisible by eight.
You will notice that there is a nice simple divisibility rule listed above for every number up to ten… except seven. The only divisibility rule I had ever seen for seven was rather complicated and hard to perform in one’s head, making it rather useless. At least, I think it was, because I don’t remember it.
But just today, I read an excellent post over at Foxmaths! explaining—complete with derivation—a nice divisibility rule for seven. The rule is this: take the number, and subtract twice the final digit from the number formed by the remainder of the digits. The result will be divisible by seven if and only if the original number was. Of course, this process can be repeated until you’re left with something simple. For example, imagine starting with 3641: subtract twice 1 from 364, giving 364 – 2 = 362. Now subtract twice two from 36, giving 32, which is not divisible by seven. Therefore, 3641 isn’t, either. See, nice and simple!
The really neat thing is that this isn’t peculiar to seven—Fox goes on to show how the same technique can be used, in principle, to derive a similar divisibility test for any prime number! Go read it.
The Math Less Traveled 
I was even able to show, though I don’t think I’ll post on this, that any divisibility rule you generate is going to be relatively simple with respect to the divisor. For example, the rule for 41 is you multiply the last digit by 4 and subtract it from the others. Neat stuff.
Oh, the link on your blogroll is kind of out of date …
Fox: neat stuff indeed. I’m inspired to play around with it a bit myself. I have a few other thoughts, maybe I’ll post more on it later. Re: the link, thanks for the heads-up, I’ve fixed it now!
Yes, I wonder if the divisible-by-7 rule is still more trouble than it’s worth, though. It’s still interesting, either way.
A commenter on Fox’s site points out that the divisibility rule for 11 is relatively easy: alternately add and subtract the digits, and see if the result is divisible by 11. For example 37241398 -> 3 – 7 + 2 – 4 + 1 – 3 + 9 – 8 = -7 or something, so it’s not divisible by 11.
In base 6, we can get quite far with quite simple divisibility rules; a number is:
* divisible by 2 iff its last digit is,
* divisible by 3 iff its last digit is,
* divisible by 4 iff the number formed by its last two digits is,
* divisible by 5 iff the sum of its digits is,
* divisible by 6 iff its last digit is,
* divisible by 7 iff the alternating sum of its digits is (like 11 in base 10),
* divisible by 8 iff the number formed by its last three digits is,
* divisible by 9 iff the number formed by its last two digits is, and
* divisible by ten iff it’s divisible by both 2 and 5.
In base twelve, we can get even further, with only one appeal to Fox’s generalized divisibility trick, because we can use this trick for both 5 and 7 at the same time: a number 12*A + B is divisible by 5 or 7 iff A + 3*B is. Then, in general, a number is:
* divisible by 2, 3, 4, 6, or twelve iff its last digit is,
* divisible by 5 or 7 iff (see above),
* divisible by 8, 9, or sixteen iff the number formed by its last two digits is,
* divisible by ten iff it’s divisible by both 2 and 5,
* divisible by eleven iff the sum of its digits is,
* divisible by thirteen iff the alternating sum of its digits is,
* divisible by fourteen iff it’s divisible by both 2 and 7, and
* divisible by fifteen iff it’s divisible by both 3 and 5.
Tim: heh, well, I guess that depends what it’s worth, doesn’t it? =) I can do the divisible by 7 rule iteratively in my head much faster than I could do a trial division by 7 in my head, which is not true for the alternating-sums-of-groups-of-three rule which is the other rule I’ve seen for 7. But anyway, thanks for the analysis of base 6 and base 12! Memorizing rules for base 6 and base 12, though, is definitely more trouble than it’s worth. 😉
I happened to learn the seven method sometime in the last year, having seen a harder one in fourth grade (unless it was the same and I just wasn’t ready for it). It’s useful for testing whether a number is prime, which is something I do now and then for diversion.
Brent,
My 7th grade math teacher taught us the divisibility by 7 rule you list here, not the sums of groups of 3. I guess I had a stronger foundation in junior high level math than you . . . how remarkable you managed to overtake me eventually 😉
Having not used it once since then I’d forgotten it anyway. As an homage to 7, though, the best single-digit number, I do set my watch seven minutes fast: I like to have a fast watch to help me get places on time, and I’ve always found 7 to be the hardest number to subtract.
Pondering base 16, we get the following:
2, last digit
3, sum of digits
4, last digit
5, sum of digits
6, 2 and 3
7, use Fox’s trick, 16A+B is congruent to A+4B mod 7 (and mod 9)
8, last digit
9, same as 7
10, 2 and 5
11, Fox’s trick again, but this time 16A+B is congruent to A-2B mod 11
12, 3 and 4
13, yet another Fox trick, with 16A+B congruent to A-4B mod 13
14, 2 and 7
15, last digit
In fact, I see a generalization; for any multiple-of-four base 4X, A+XB provides a test for 2X-1 and 2X+1.
silverpie: nice analysis! I should point out one technicality, however, which is that it is incorrect to say, e.g. “16A+B is congruent to A+4B mod 7”. In fact, it is only the case that 16A+B is divisble by 7 if and only if A+4B is. This is not the same as being congruent. For example, if we take A=2 and B=4, we have 16*2 + 4 = 36, which is 1 mod 7, and 2 + 4*4 = 18, which is 4 mod 7. If you read Fox’s original post carefully you will see the distinction and why it arises.
There is also a nice rule for divisibility by 11. If one adds and sutracts alternate digits then if the result is divisible by 11 then the original number is. This follows form the fact that (our bas) 10=-1 modulo 11. The adding digits test for divisibility by 9 (and 3) follows from the fact that 10=1 modulo 9 (3). In general in base B we always have a nice test for divisibility by B-1 (adding digits) and B+1 (adding and subtracting alternate digits). This makes base 12 a “better” choice of number system than 10 as we have a test for divisibility by 13, which is more useful that a test for 9 or 3 (both of which give nice results in base 12 anyway).
Here’s another test for 7 … starting from the leftmost digit and proceeding to the right, triple what you have and add the next digit …
1342 -> 1 *3+3=6 *3+4=22 *3+2=68 and 68 -> 6 *3+8=26 which is not divisisible by 7 so neither is the original number.
You can simplify by dropping multiples of 7 at will …
1342 -> 1 *3+2=6 *3+4=22=1(mod 7) *3+2=5 so dividing 1342 by 7 leaves remainder 5. This is better than the above test because it preserves the remainder.
I recently found another test for 11.
Take the number in the ones place and subtract it from the truncated number. If the difference is divisible by 11, so is the original number
Consider the number 847.
84-7 = 77
Yes! Divisible by 11
1342
134-2 = 132 (Some will see that it is divisible here, otherwise…)
13-2 = 11
Yes! Divisible by 11
757
75-7 = 68
No. Not Divisible by 11.
Can be a tad bit cumbersome for longer numbers, but it works well for 3 to 5 digit numbers.
Jennifer: good work! In fact, this test for 11 is also an instance of the general method that Fox originally wrote about. Like the rule for 7, it doesn’t preserve the remainder mod 11, but it does preserve divisibility/non-divisibility by 11.
divisibility by 11 is also easy.
Starting with the number abcdefg, where a, b, c, etc. are all, independently, single digits;
Let X = the sum of every other digit; i.e., X = a+ c + e ; and
let Y = the sum of the other series of every other digit, i.e., Y = b + d + f;
If the absolute value of X minus Y is divisible by 11, so is abcdefg!
It works for any number, without limit to the number of digits in abcdefg….!