Most people are aware of two or three basic tests for divisibility by a prime number:
- A number n is divisible
- by 2 iff it ends in an even number (0, 2, 4, 6, or 8)
- by 5 iff it ends in a 0 or a 5
- by 3 iff its digits add up to a multiple of 3
These can be expanded to composites:
- A number n is divisible
- by 4 iff its last two digits are divisible by 4 (that is, if it can be divided by 2 twice)
- by 6 iff it is divisible by both 2 and 3
- by 8 iff its last three digits are divisible by 8 (that is, if it can be divided by 2 three times)
- by 9 iff its digits add up to a multiple of 9 (that is, if it can be divided by 3 twice)
Famously absent from this traditional list is a test for divisibility by 7. This test, in isolation, is difficult to apply:
- A number n is divisible by 7 iff, when you truncate the last digit, double it, and subtract it from the remainder, you get a multiple of 7
- For instance, 28 is a multiple of 7 because 2 – 8 * 2 = -14, which is a multiple of 7
Applying this rule for a single case seems too labor-intensive. It’s usually easier just to divide the number by 7.
However, today I found a general technique for creating divisibility rules for any prime number.
First, I’ll lay it out algebraically.
- Let p be a prime number, and let \(10m + 9\) be a multiple of p. Then \(10a + b \equiv a + (m + 1)b \mod p\).
- Let p be a prime number, and let \(10n + 1\) be a multiple of p. Then \(10a + b \equiv a – nb \mod p\).
More casually speaking, here’s the technique:
- For a prime number, find the lowest multiple that ends in a 1 or a 9.
- Remove the last digit from the multiple. If it’s a 9, then add one to the remaining digits. If it’s a 1, just use the remaining digits as is. Call this the multiplier.
- If the last digit of the multiple is a 1, then use subtraction; if it’s 9, use addition. Call this the operator.
- To find out if a given number is divisible by a given prime:
- Take off the last digit and multiply it by the multiplier
- Using the correct operator, find the sum or difference between this and the rest of the given number
- Repeat A and B until you have a multiple you recognize
Note that you only have to do the first three steps once for each prime; then you can just create a list of multipliers and operators:
| Prime | Multiplier | Operator |
| 3 | 1 | + |
| 7 | 2 | – |
| 11 | 1 | – |
| 13 | 4 | + |
| 17 | 5 | – |
| 19 | 2 | + |
| 23 | 7 | + |
| 29 | 3 | + |
| 31 | 3 | – |
| 37 | 11 | – |
| 41 | 4 | – |
| 43 | 13 | + |
| 47 | 14 | – |
Examples
Here are some examples.
Is 61712 divisible by 7?
- 21 is the lowest multiple of 7 that ends in a 1 or 9.
- It’s a 1, so use 2 as the multiplier.
- It’s a 1, so use subtraction.
- 61712:
- 2 x 2 = 4
- 6171 – 4 = 6167
- 7 x 2 = 14
- 616 – 14 = 602
- 2 x 2 = 4
- 60 – 4 = 56
- 6 x 2 = 12
- 5 – 12 = -7
So 61712 is divisible by 7 (which it is).
Is 61712 divisible by 13?
- 39 is the lowest multiple of 13 that ends in a 1 or 9.
- It ends in 9, so use 3 + 1 = 4 as the multiplier.
- It ends in 9, so use addition.
- 61711:
- 1 x 4 = 4
- 6171 + 4 = 6175
- 5 x 4 = 20
- 617 + 20 = 637
- 7 x 4 = 28
- 63 + 28 = 91
91 is a multiple of 13, so 61712 is too.
Note that this also works with 3. 9 is the lowest multiple of 3 that ends appropriately, so the multiplier is 1 and the operator is addition. In other words, add the last digit to the rest, and repeat; this is the traditional rule, expressed recursively.
Here Be Monsters
The explanation for why this works relies on some modular arithmetic. If you’d rather just say, “Hey, that’s neat” and move on, you’re excused from the table. If you’d like some dessert, hang out a bit longer.
First, let’s consider the case where the multiple of p ends in 9. That is, there is some multiple of p that can be expressed as \(10m + 9\). I wrote this formally above as \(10m + 9 \equiv 0 \mod p\).
What we want to know is if a given number n is a multiple of p. If n has more than one digit, we can write \(10a + b = n\). The question is whether \(10a + b \equiv 0 \mod p\). (For the rest of this discussion, all equivalence will be mod p.)
Let us then create a new value, \(a + (m + 1)b\). Our claim is that \(a + (m + 1)b \equiv 0\) when \(10a + b \equiv 0\). Note that \(10m \equiv -9\).
If a given number is equivalent to 0 in a particular modulus, then all multiples of that number are likewise equivalent. So \(10a + 10(m + 1)b \equiv 0\). In this case, \(10a + 10(m + 1)b \equiv 10a + b\) and therefore \(10mb + 10b \equiv b\). From here it follows that \(10mb \equiv -9b\). This is true when \(10m \equiv -9\), q.e.d.
Note that the converse is not necessarily true: We can’t use this method to determine how far off the original number is from being a multiple. 61712 is one more than 61711, but it yields 6179 in its first step, which is four more than 6175. This is because we’re multiplying one of the equivalences by 10; if \(a + (m + 1)b \equiv c\), then \(10a + 10(m + 1)b \equiv 10c\). \(10c \equiv c\) is only reliably true then \(c = 0\). Four times ten is forty, and \(40 \equiv 1 \mod 13\), so the mathematics works out.
Let’s now consider the case where the multiple of p ends in 1: \(10m + 1 \equiv 0\). We want to know if \(10a + b \equiv 0\), using \(a – mb \equiv 0\). Note that \(10m \equiv -1\).
So \(10a + b \equiv 10a – 10mb\) and \(b \equiv -10mb\). Dividing both sides by \(-b\) gives us \(-1 \equiv 10m\), q.e.d.
Hence, if \(a – mb\) or \(a + (m + 1)b\) is divisible by \(p\), so too will \(10a + b\) be.
To wrap up, let’s consider the case of 2 and 5. These work because of our base ten system; for other bases, other rules would be needed. Since \(n = 10a + b\) and \(10a \equiv 0\) for both \(p = 5\) and \(p = 2\), that means \(10a + b \equiv b\) for both \(p = 5\) and \(p = 2)\.