There’s this divisibility trick. Say you want to know if a number is divisible by 3. Add all the digits together. The original number is divisible by 3 if and only if the result is. Let’s check 2353 as an example. 2+3+5+3=13. 13 is not divisible by 3, so neither is 2353. What’s going on here?
Let’s call the original number and split it up into . That way we can look at the most significant digit and the rest of the number separately, and apply this repeatedly to get something like the 3-divisibility trick. Let’s call the number we are checking for divisibility by . We take and add and subtract .
For those not familiar with , it’s called “mod”, short for modulo, has the same precedence as multiply and divide, and gives the remainder of the left number divided by the right number. , so it is divisible by , is with some multiple of added or subtracted, so it is divisible by , so is divisible by . This means
is divisible by if and only if is divisible by .
So let’s see what this means when we are checking if 2353 is divisible by 3. . So is divisible by 3 if and only if is. We split 2353 into 10(200)+353, so and . So 2353 is divisible by 3 if and only if is divisible by 3. We don’t know if 553 is divisible by 3, so we let and and we add to get 103. We don’t know if 103 is divisble by 3, so we let and and we add to get 13. 13 is not divisible by 3, so neither is 103, so neither is 553, so neither is 2353. Because all we ever did was add the most significant digit to the next most significant digit, we can summarize this as “add all the digits”.
What about dividing by 11? This is another common one, you add every other digit starting with the most significant and see if it’s equal to the sum of every other digit starting at the second most significant. The number is divisible by 11 if and only if the two sums are equal. So, consider 35794. First we add every other digit starting with the most significant, so we have 3+7+4=14. Then we add every other digit starting with the second most significant, so we have 5+9=14. Because they are equal, 35794 is divisible by 11.
What happens when we use the general formula? . Now, some of you might be disturbed that I said (-1)%11=-1, and would have expected (-1)%11=10. Basically, we want something that is easy to apply, so taking a negative number as the result of a mod is good when the negative number has a smaller absolute value than the positive alternative. You can go through the steps, but this turns out to be “subtract every other digit starting with the most significant and add every other digits starting with the second most significant, and see if the result is divisible by 11” which is equivalent to the common 11-divisibility rule. Another thing that might disturb some of you is when I take 0 as divisible by 3 or 11 or whatever. Basically if you’re not comfortable with that, I’ll go ahead and redefine what “divisibility” means to be “m is divisible by n if and only if m%n=0”.
Let’s try a number no one has a trick for, 13. . Let’s interpret this as “multiply the most significant digit by -3 and add it to the next most significant digit”. And let’s make a notation system that lets us compute these things faster. We’ll see if 453609 is divisible by 13. First we write out the digits separately in a list
4 5 3 6 0 9
We multiply the most significant digit, 4, by -3, get -12, add that to the next most signficiant digit, 5, get -7, and put it in place of the 5.
-7 3 6 0 9
Next we take -7, multiply by -3 to get 21, and add that to 3 to get 24, and put that in place of the 3.
24 6 0 9
Now, it’s a bit annoying to multiply 24 and 3. So we remember what this whole thing represents. 24 is just a digit of some number. I know digits are supposed to be between 0 and 9. So really we have to remember what digits represent, which is powers of 10. When we subtract 13 from a digit, we have subtracted 13 times some power of 10 from the number we are representing. Because 13 times some power of 10 is divisible by 13, the original number and the new number have equivalent 13-divisibility. So let’s subtract 13 from 24, and then continue like before from there.
11 6 0 9
-27 0 9
We do the same thing as we did before with the -27, only this time we add 13, twice.
-1 0 9
At this point we can stop because we know 39 is divisible by 13, so 453609 must be as well.
Let’s do one more example, checking the divisibility of 288048 by 7. . I’m going to use “MSD” to mean “most significant digit” and “NMSD” to mean “next most significant digit”.
2 8 8 0 4 8 — multiply MSD by 3 and add to NMSD
14 8 0 4 8 — replace MSD with MSD%7
0 8 0 4 8 — remove MSD because it is 0
8 0 4 8 — multiply MSD by 3 and add to NMSD
24 4 8 — replace MSD with MSD%7
3 4 8 — multiply MSD by 3 and add to NMSD
13 8 — replace MSD with MSD%7
5 8 — multiply MSD by 3 and add to NMSD
At this point we can see 23 is not divisible by 7, so neither is 288048.
Say we wanted to check for divisibility by 20. Then . Uh oh. We’ve arrived back at our original split representation of . So let’s extend our trick for numbers 20 or greater. Let’s instead split into , which will have the same divisibility by as . We’ll check the divisibility of 5421583 by 23. , so we take the MSD, multiply by 8, and add to NMSD. Because we’ve split differently this time, our shorthand will be different. So we really aren’t even talking about digits anymore, but we’ll just stay with it because of the easy analogy.
54 21 58 3 — replace MSD with MSD%23
8 21 58 3 — multiply MSD by 8 and add to NMSD
85 58 3 — replace MSD with MSD%23 (-7 is easier than 16, so we use -7)
-7 58 3 — multiply MSD by 8 and add to NMSD
We have to stop here because the 3 is not a pair of digits like every other entry in the list. At least, we’d have to change the math to match. But it doesn’t matter, because this represents the number 23, which is divisible by 23, so 5421583 is divisible by 23.
This modification of the trick should work up to . For you'd need to switch to the set of tricks based on 1000 as opposed to 100 or 10. In general, for you split into .
Happy divisibility checking!