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.