There is a simple trick for checking if a number is divisible by \(7\). It goes like this:
First, separate the number into two parts: everything except the last digit, and the last digit. For example: \(343\) separates into \(34\) and \(3\).
Then, take the first part, and subtract two times the second part. In our working example: \(34 - 2\cdot 3 = 28.\)
Now, if this number is divisible by \(7\), then so is our original number! Otherwise, we are out of luck. We know \(28\) is divisble by 7. However, if our number at this step is still large, we can just repeat the process again!
This got me thinking: is \(7\) special, or do other numbers have a similar rule? So, I set out to explore this on a flight from Iowa back to Boston around three months ago.
We begin by proving the following fact[1], which will in turn give us the general rule for divisibility by \(n\): For any \(r\) such that \(10r \equiv 1\bmod n\), we have that \[\sum_{k=1}^\infty 10^{k-1}a_k + ra_0\equiv 0 \bmod n \text{ iff } \sum_{k=0}^\infty 10^ka_k \equiv 0\bmod n. \] To prove the forward direction, we simply multiply both sides by \(10\), and note that \(10ra_0 \equiv a_0 \bmod n\). For the reverse direction, multiply both sides by \(r\), and separate the sum into \(k=1\) to \(\infty\) and \(k=0\). The \(10r\) factor in the former sum can be dropped by our initial assumption!
How is this fact relevant? In our example above: the number \(343\) is equivalent to \(3\cdot 10^2 + 4\cdot 10^1 + 3\cdot 10^0\). In other words, if we write \(343\) as its sequence of digits from left to right: \(a_2 = 3, a_1 = 4, a_0 = 3\) (admittedly not the best example due to its palindromic nature), we can write it as a sum of multiples of powers of 10, where the multiples are exactly its digits. We use this representation to abstract out the rule: in the case of the rule for \(7\), the number we obtain after separating and subtracting is \(\sum_{k=1}^\infty 10^{k-1}a_k - 2a_0\).
So, what this rule translates to is: separate the number as above. Then, take the first part and add \(r\) times the last digit to it (which gives us \(\sum_{k=1}^\infty 10^{k-1}a_k + ra_0\), exactly as in the fact). If this is divisible by \(n\), then our original number is divisble by \(n\)![2] Otherwise, we conclude it is not divisible.
Now, how do we find \(r\)? Does it even exist for all \(n\)? The answer is no - \(n\) must be coprime with \(10\). [This actually rules out 60%[3] of numbers :(] You can find \(r\) by simple trial and erroring through \(1\) through \(n-1\).
An easy way to think of what this gives for \(r\) is to first find the first number that ends in \(9\) that is divisible by \(n\). Then, add \(1\) and divide by \(10\) to obtain \(r\).
Let's do an example! Let's try out the divisibility rule for \(23\). \(69\) is divisble by \(23\) - hence \(7\) is a valid value of \(r\). Is \(7751\) divisible by \(23\)? Let's apply the rule. \(7751 \rightarrow 775 + 7\cdot 1 = 782 \rightarrow 78 + 7\cdot 2 = 92\) which is \(4\) times \(23\)! Or if you would like to go a step further, \(92 \rightarrow 9 + 7\cdot 2 = 23\). Either way, we get divisibility by \(23\)!
One final note! You may be asking: "But this doesn't seem to match up with the divisibility rule for \(7\) we started with?" Here's the thing: notice that in the main fact, \(r\) doesn't have to be positive. Using the procedure I described above for finding \(r\), we would find \(r\) to be \(5\), as \(50-1\) is divisible by \(7\). Once we find an initial \(r\), you can add or subtract any multiple of \(n\) to get a new \(r\). So for \(n=7\), we can even use \(r = 5 - 7 = -2\). This is more appealing because multiplying by \(2\) is easier than multiplying by \(5\)! (Although, arguably, subtracting might be harder than adding... ;)