Divisibility Testing for 7

Everyone learns how to test numbers for divisibility sometime around the 3rd or 4th grade, I think. Tests for 2 and 5 are trivially simple. Tests for 3 and 9 are nearly as simple, owing to some magic to do with 9 being one less than the base of the number system we use^*.

Testing 4 works by virtue of the fact that only the last two digits matter. For example, does 86,753,096 divide by 4? Since 100 divides by 4, you can ignore 86,753,0__ and focus on the 96 part. Then the rule is, if the 10's digit is odd, the 1's digit has to be 2 or 6; if 10's are even, 1's have to be 0, 4, or 8.

Testing 6 comes down to (a) is it even? and (b) does 1/2 of it test for 3?

But it seems like most people are told there isn't an easy test for 7. But wait! If your number divides by 7, then you should be able to take 7 away from it any number of times, and the difference will also divide by 7. Taking a multiple of 7 away from the number under test preserves its modularity with respect to 7, which means that the remainder after actually doing the division will be the same. We can use this to shrink a large number down into a smaller number that is easier to test.

So, here's how to test for 7:

First, if your number starts with a 7, you can just drop that off immediately, which is equivalent to subtracting off 70, or 700, or even 70,000,000,000,000; you get the idea.

Next you can get rid of unpleasant digits like 8 or 9 by just subtracting 7 from them where they are. For example, 1891 ÷ 7 is the same as 1121 ÷ 7, because all you did was take away 700, and then 70.

Now consider the number 1001; it turns out that 1001 = 7 * 11 * 13. Any multiple of 1001 is therefore also a multiple of 7. This means you can take away the leading digit of your number if you also subtract it from the 4th digit in!


Here's an example: does 186,753,091 divide by 7?

First get rid of that leading '1' by subtracting off 100,100,000:
186,753,091 – 100,100,000 = 86,653,091 .. shorter by one digit.

Can we do it again? Well, looking at 86,653,091, maybe we could take out 80,080,000 but that leaves 5 – 8 at the fourth place. But remember, in mod 7 arithmetic '8' and '1' are the same thing (as are '9' and '2'). So the leading '8' can be turned into '1' by subtracting 70,000,000 which is yet another multiple of 7. So now the problem is:

16,653,091 – 10,010,000 = 6,643,091

Now we're going to add a multiple of 7 to get rid of the leading 6!

6,643,091 + 1,001,000 = 7,644,091 which becomes 644,091

Do the same thing again to get rid of the leading 6: add 100,100 to get 744,191 and drop the leading 7 and all that's left is 44,191

Now eliminate the leading 4 by removing 40,040 = 4 * 1001 * 10

44,191 – 40,040 = 4,151

Hmm.. 1 – 4 at the last digit? Nah. Go up! Add 3,003 = 3 * 1001

4,151 + 3,003 = 7,154 which becomes 154

And now you have a three digit number and 1001 is no more use. Sadly, the only way out is to just divide whats left by 7, but at least this is better than doing the whole nine digit number. With very little practice, you can look at a large number and almost just write down the three-digit result.

---

^* What works for 9 in base 10 also works for 4 in base 5, 7 in base 8, even 15 in hexadecimal, as long as you add up the digits in the base you're testing in!