Many of us have learned that to test if a number is divisible by 3, all we have to do is sum the digits of that number and see if the sum is divisible by 3.

For example, is 3732 divisible by 3? To find out, we see that \(3 + 7 + 3 + 2 = 15\) and since 15 is divisible by 3 so is 3732. We can verify this since \(1244\cdot 3 = 3732\).

Here is a list of divisibility rules for integers commonly taught to schoolchildren:

• An integer is divisible by 2 if the units digit is divisible by 2.
• An integer is divisible by 3 if the sum of the digits is divisible by 3.
• An integer is divisible by 4 if the two digit number formed by the last two digits is divisible by 4.
  • 2349328492024 is divisible by 4 because 24 is divisible by 4.
• An integer is divisible by 5 if the units digit is either 0 or 5.
• An integer is divisible by 6 if the integer is even and the sum of the digits is divisible by 3.
• An integer is divisible by 8 if the three-digit number formed by the last three digits is divisible by 8.
• An integer is divisible by 9 if the sum of the digits is divisible by 9.
• An integer is divisible by 10 if the units digit is 0.
• An integer is divisible by 11 if the alternating sum of the digits is zero. <edit per jonathanvt’s comment: if alternating sum of the digits is zero OR ELEVEN> <edit edit because I’m a sloppy fool … An integer is divisible by 11 if the alternating sum of the digits is divisible by 11>
  • 6941 is divisible by 11 because \(6 – 9 + 4 – 1 = 0\).
  • 9614 is divisible by 11 because \(9 – 6 + 1 – 4 = 0\).
  • 9641 is not divisible by 11 because \(9 – 6 + 4 – 1 = 6 \neq 0\).
  • 40909 is divisible by 11 because \(4 – 0 + 9 – 0 + 9 = 22\) which is divisible by 11.

But what happened to seven? Is there no divisibility rule for seven? And what about numbers greater than 11, are there no divisibility rules for those numbers? Alas, a common misbelief is that there are no divisibility rules for numbers other than the ones given above. The truth is, there are divisibility rules for all numbers; they are just not as “practical” (read: memorizable) as those that were shown in arithmetic classes.

With that said, let’s try a few things. It may be cryptic at first, but just humor the author, he’ll eventually make his point.

Some examples

In this section, I want to first convince you by way of examples / patterns that there ought to be a divisibility rule. Then, I’ll show you the math.

Here’s our times table for seven that we’ll want to keep handy.

\(7 \cdot 1 = 7\)	\(7 \cdot 8 = 56\)
\(7 \cdot 2 = 14\)	\(7 \cdot 9 = 63\)
\(7 \cdot 3 = 21\)	\(7 \cdot 10 = 70\)
\(7 \cdot 4 = 28\)	\(7 \cdot 11 = 77\)
\(7 \cdot 5 = 35\)	\(7 \cdot 12 = 84\)
\(7 \cdot 6 = 42\)	\(7 \cdot 13 = 91\)
\(7 \cdot 7 = 49\)	\(7 \cdot 14 = 98\)

Now for the part where you have to humor me. Wrinkle your brow if you must, but don’t go away!

Let’s take a look at 14. This number is divisible by 7 because \(1\cdot 3 + 4\cdot 1 = 7\) and since 7 is divisible by 7, so is 14.

Let’s take a look at 42. This number is divisible by 7 because \(4\cdot 3 + 2\cdot 1 = 14\) and since 14 is divisible by 7, so is 42.

What?

Well, maybe there’s a pattern.

Let’s take a look at 476. This number is divisible by 7 because \(4\cdot 2 + 7\cdot 3 + 6\cdot 1 = 35\) and since 35 is divisible by 7, so is 476.

So here’s the “process” using the number 367423.

1. Write 367423 as sequence of one-digit numbers in reverse order. Thus, 3,2,4,7,6,3.
2. Write out the sequence 1,3,2,6,4,5. (I’ll explain where this comes from later. For now, humor me!)
3. Multiply term-by-term the sequence in Step 1 with the sequence in Step 2 to get the sequence 3,6,8,42,24,15.
4. Add together all the numbers in the sequence in Step 3 to get 98.
5. Since 98 is divisible by 7, so is 367423. Indeed, \(52489 \cdot 7 = 367423\).

If we have a number with more than six digits, then just follow the same steps, except repeat the sequence in Step 2. In other words, for a seven-digit number use 1,3,2,6,4,5,1 as the sequence in Step 2.

The rule, formally

Now, let me explain the rule formally for checking divisibility of seven. Then I’ll show you where the rule comes from and how you can find the rule for any number. You can skip this section and just go to the derivation if you like.

Let \(m\) be the repeating sequence \(1,3,2,6,4,5\). Thus, we may write \(m_{1} = 1\), \(m_{2} = 3\), \(m_{3} = 2\), \(m_{4} = 6\), \(m_{5} = 4\), and \(m_{6} = 5\). Since this is a repeating sequence \(m_{7} = m_{1} = 1\). A more condensed notation is \(m_{i} = m_{(i \mbox{ mod } 7) + 1}\) for \(i \geq 7\) and where \(\mbox{ mod }\) is the modulus. In other words, \(m_{7}\), \(m_{14}\), \(m_{21}\), \(m_{7i}\) all equal \(m_{1}\); \(m_{8}\), \(m_{15}\), \(m_{22}\), \(m_{7i+1}\) all equal \(m_{2}\) and so forth. The sequence is just repeating in the pattern of \(1,3,2,6,4,5,1,3,2,6,4,5,\ldots\).

Now, consider a number \(K\) of \(n\) digits (I’m not going to get pedantic about leading zeros) and write it out in terms of its digits as follows \(K = a_{n}a_{n-1}\ldots a_{2}a_{1}\), where \(a_{1}\) is the ones place, \(a_{2}\) is the tens place, \(\ldots, a_{n}\) is the \(10^{n-1}\) place.

Then, let \(S = \sum_{i=1}^{n} a_{i}m_{i}\). If \(S\) is divisible by 7 so is \(K\).

A derivation

A derivation of this rule is actually pretty straight forward.

Let \(a_{0}, a_{1}, a_{2}, \ldots, a_{n-1}\) be the digits of an \(n\)-digit number, with \(a_{0}\) representing the ones place, \(a_{1}\) representing the tens place, and so forth in powers of 10. Let \(K\) be this \(n\)-digit number. Therefore, we may write $$K = \sum_{i = 0}^{n-1}a_{i}10^{i}$$

If \(K\) is divisible by 7, then \(\sum_{i = 0}^{n-1}a_{i}10^{i}\) must be divisible by 7. Writing the sum and dividing by 7 explicitly, we have $$\frac{\sum_{i = 0}^{n-1}a_{i}10^{i}}{7} = 1\frac{a_{0}}{7} + 10\frac{a_{1}}{7} + 100\frac{a_{2}}{7} + \cdots + 10^{n-1}\frac{a_{n-1}}{7}$$

Now, for the final algebraic step. We just have to recognize that \(10 = 7 + 3\), \(100 = 98 + 2\), \(1000 = 994 + 6\), \(10^{n-1} = 7 \cdot \mbox{int}(10^{n-1}\div 7) + R\), where \(\mbox{ int }\) represents the integer portion of the division and \(R\) represents the remainder. Now, we should be able to see that in order for \(K\) to be divisible by 7, we have to have $$\frac{1a_{0} + 3a_{1} + 2a_{2} + 6a_{3} + \cdots + Ra_{n-1}}{7}$$ be divisible by 7. Notice that the coefficients of the \(a_{i}\) are the sequence in Step 2 in the “process” (or \(m\) if you read the previous section). The sequence repeats itself because the decimal expansion for \(\frac{1}{7}\) repeats.

Exercises

Can you derive a divisibility rule for 3? Here’s a hint: \(1 = 0 + 1\), \(10 = 9 + 1\), \(100 = 99 + 1\), \(1000 = 999 + 1\).

Can you derive a divisibility rule for 11? Here’s a hint: \(1 = 0 + 1\), \(10 = 11 – 1\), \(100 = 99 + 1\), \(1000 = 1001 – 1\).

Can you derive a divisibility rule for 12? Here’s a hint: \(1 = 0 + 1\), \(10 = 12 – 2\), \(100 = 96 + 4\), \(1000 = 996 + 4\).

Based on what you saw for divisibility rules for 2, 4, and 8, can you guess what divisibility rules for 16, 32, 64, 128, \(2^{n}\) would be?

Can you see the connection with these divisibility rules and \(\frac{1}{\mbox{divisor}}\)?

If we were counting in base 7, can you show that a (the) divisibility rule for 7 would be “the ones place has to end in zero”?

Why do I keep saying “a” divisibility rule and not “the” divisibility rule?

Can you show that the sequence beginning with -1, followed by an infinite run of 2s can be a divisibility rule for 3? For example, 2385 is divisible by 3 because \(-5 + 8\cdot 2 + 3\cdot 2 + 2\cdot 2 = -5 + 16 + 6 + 4 = 21\) and since 21 is divisible by 3, so is 2385. Hint: \(1 = 0 + 1, 10 = 12 – 2, 100 = 102 – 2, 1000 = 1002 – 2\).