A year ago, Numberphile gave methods to check for divisibility by integers from 2 to 12. But these methods are so many and varied, it is mentally difficulty to remember which method to use with which divisor.
https://www.youtube.com/watch?v=UDQjn_-pDSs
https://www.cuemath.com/numbers/divisibility-rules/
Numberphile recently gave several other methods to check for divisibility by 7.
https://www.youtube.com/watch?v=Ki-M1DJIZsk
One of these was amenable to mental operations, but they failed to generalise it to a mental method for divisibility by other small integers. I'm going to do that below, in a way that gives a single method for checking divisibility by integers from 2 to 13, and gives the well known methods for 2, 5, 10, 3 and 9 as special cases.
No matter what small divisor d you're interested in, the method begins by generating from that divisor, an even smaller integer, typically between -3 and +3. We'll call it the divisor's magic multiplier m. I'll explain how to get m from d later.
The method then proceeds through the digits of the large integer as follows:
Begin with the most significant digit
Reduce it modulo d
Repeat
Multiply by m
Add this to the next most significant digit
Reduce modulo d
Until no more digits
If the result is zero, then the original number was divisible by d.
To reduce a number modulo d we subtract from it the largest multiple of d that is less than or equal to it. For example, to reduce 27 modulo 7 we subtract 21 (=3×7), leaving 6.
Let's see if 987 is divisible by 7. For divisibility by 7, the magic multiplier is 3.
Start with the the most significant digit 9 Reduce the 9 mod 7 = 2 Multiply the 2 by 3 = 6 Add the 6 to the next digit 8 = 14 Reduce the 14 mod 7 = 0 Multiply the 0 by 3 = 0 Add the 0 to the next digit 7 = 7 Reduce the 7 mod 7 = 0
So 987 is divisible by 7.
Any of the "Reduce modulo d " steps can be omitted, except the final one. It just means that the following multiplication, addition and reduction may be a little more difficult. In fact the whole algorithm is a reduction modulo d, so it can be applied recursively as its own final reduction step. But the point of the above version, with a reduction after every digit addition, is that no reduction requires you to know any multiple of d beyond 3d. For mentally checking divisors of 7 and 13 it's pretty much necessary to do every reduction.
We could actually do more reductions. We could do one after every multiplication as well as after every addition. This would mean we'd only need to know multiples of the divisor up to 2d. But this makes it difficult to keep track of where we are in the mental process. "I just did a reduction, am I now due for a multiplication or an addition?" Whereas, in the algorithm above, only a multiplication ever follows a reduction.
Now, how do we obtain the magic multiplier m from the divisor d? It's just the smallest-magnitude integer equivalent to 10 mod d.
d m ≡ 10 mod d ---------------- 2 0 3 1 4 2 5 0 6 4 7 3 8 2 9 1 10 0 11 -1 12 -2 13 -3
Note that, for divisors from 6 to 13, m is simply 10-d.
We have one case where m is outside of -3 to +3. We can still use m = 4, however, testing for divisibility by 6 is more easily done by testing for divisibility by both 2 and 3. The same goes for 12 (3 and 4), 14 (2 and 7) and 15 (3 and 5). The only divisors that need a single test are the primes 2, 3, 5, 7, 11 and 13, and the prime powers 4, 8, and 9.
You can see why 2, 5 and 10 only require us to look at the least significant digit. All the previous digits get multiplied by 0.
And you can see why no multiplication is required for 3 and 9. Their magic multiplier is 1, so their algorithm reduces to:
Begin with the most significant digit
Repeat
Add this to the next most significant digit
Reduce modulo d
Until no more digits
11 and 13 are a little more difficult because their magic multiplier is negative, but we can just use the following equivalent algorithm involving subtraction:
Begin with the most significant digit
Repeat
Multiply by -m (when m is negative, -m is positive)
Subtract this from the next most significant digit
Reduce modulo d
Until no more digits
And for 11 this reduces to:
Begin with the most significant digit
Repeat
Subtract this from the next most significant digit
Reduce modulo d
Until no more digits