Divisibility tests

We take a lot of things for granted nowadays. One of those things is how easy it is to spot if a number is even or odd. 14? Even. 17? Odd. 256? Even, 1337? Odd. 4,896,352,891,228 is even, 6,713,189,283 is odd. All you have to do is look at the last digit. Same with multiples of five, or ten. Just look at the last digit. It’s so nice. So clean. So easy. Not like other numbers, where your best bet is just to perform long division until you see whether or not it’s a multiple.

But then again, there are some tricks. Take 3 for example: you can just add up the digits. 365 is not a multiple of 3 since 3+6+5 = 14. But 5586 is; 5+5+8+6 = 24. Indeed 5586 = 3×1862. Adding up the digits didn’t help us figure out by what 5586 is a multiple of 3, just that it is one. But that’s fine I suppose, the same is true of 2 and 5.

But then if you keep digging, you keep finding little tricks like this, even if they’re not quite as nice. A number is a multiple of 7 if twice the last digit, subtracted from the number formed by the rest of the digits, is a multiple of 7. Applying this process to 343, we have a last digit of 3, and a “rest” of 34. 34-2×3 = 28 which is a multiple of 7, so so is 343. Likewise 1729 begets 172-18=154, and 15-8=7. So 154 is a multiple of 7, therefore so is 1729.

A very natural question to ask at this point might be: “Who on earth came up with all this stuff and why does it work?” Fret not, dear reader, as it is these questions precisely that this article exists to explain. The answer lies in modular arithmetic, a field of math intimately tied to cutting-edge math research, cryptography, computer science, and so much more.

And I will be going into almost none of this: In writing this article, I was overwhelmed by scope creep and so had to painstakingly keep as close to the topic at hand as possible. Today, I write about divisibility tests. One day later, I may write about those other things. Only time will tell.

I should alsoprovide a warning to the reader: this article is going to include a lot of math. In particular, there’s going to be a lot of computation, which you may find a bit tedious. I’m not your boss, so if you want to skip over that part and just skim the main ideas, then you’re free to, but just as you can’t learn to garden without getting your hands dirty, I don’t think you can learn math without some amount of chugging through the drudgery of computation.

I’d like to harken back to (or possibly introduce) the concept of long division with remainders. It looks something like this.

The quotient, 19, represents how many times the divisor, 69, can fit evenly into the dividend, 1337. But unfortunately, 69×19=1311, which is a bit shy of 1337. Indeed it’s shy by 26, so we say that in order to divide 1337 into 69 equal parts, there will be 19 groups of 69, and then 26 “remaining” that are part of no group, so the result is “19 remainder 26.”

Many students, including myself when I first learned this, find this deeply unsatisfying. After all, you could continue to divide the remainder into fractional parts to really make sure all the groups are even, and to show off just how good you are at decimal long division. Teachers will justify by saying that when you’re actually dividing things up, you can’t always cut them into smaller pieces, but that’s a very pragmatic answer. If we’re doing pure math, surely there’s no need to worry about that and we can just have a fractional answer, right?

Well here I am to tell you that no, remainders are important. In fact, they’re going to be the key to our entire puzzle, so keep them in mind as you keep reading.

Imagine, if you will, an analog clock

On a clock, everything is fine for small numbers, but it gets weird around 12. 1+1=2, so one hour after 1:00 is 2:00. And 7+5=12, so seven hours after 5:00 is 12:00. But then even though 9+8=17, nine hours after 8:00 is 5:00, not 17:00. Proponents of 24-hour time may object here and say that it actually is 17:00 and the am/pm distinction is silly. To you I will then ask, what happens ten hours after that? 27:00? No, it’s 3:00.

What’s going on here, of course, is that the time resets at 12 (or 24). We only care how long it’s been since the last 12:00. In essence, 12=0 with respect to the clock. This “clock addition” turns out to have a lot of the same properties that ordinary addition has. Namely:

• It’s commutative: a+b = b+a for all values a,b

• It’s associative: a+(b+c) = (a+b)+c for all values a,b,c

• It has a kind of zero: 12+a = a for all values a

And it’s relatively easy to see why. Ordinary addition has all of these properties, though 0 plays the role of zero, rather than 12. In general, we call this the identity. So all we need to do is show that ordinary addition is commutative and associative, then take the remainder when we divide by 12. For instance: 7+9=16 and 9+7=16, so when we convert 16:00 to 4:00, it’s the same either way. 7+9 = 4 = 9+7. Likewise, 10+(8+7) = 25 = (10+8)+7. 25:00 is just 1:00, so on the clock, we have 10+(8+7) = 1 = (10+8)+7.

Did you catch that about the remainder? That’s really all we’re doing here, adding up all the numbers and then taking the remainder of the sum. What’s interesting is that you’ll get the same result whether you take remainders at the beginning or at the end. If two numbers have the same remainder when we divide them by 12, we say they’re congruent modulo 12. If a and b are congruent modulo 12, we write a = b mod 12. Every number is congruent to something between 0 and 11 mod 12, and finding exactly what that is is called reducing mod 12.

I like to think of it as though 12 is simply made equal to zero. If two numbers have the same remainder when dividing by 12, then they’re both multiples of 12 plus that remainder: say 12×n+r and 12×m+r. If we subtract one from the other, we get 12×(n-m), and the r’s cancel out. That means the difference between the two numbers is a multiple of 12, and if 12 is now zero, then the difference is zero, therefore they’re the same, if 12 is zero. So another way to think of congruence modulo 12 is that the difference between two numbers is a multiple of 12.

Of course, there’s nothing special about 12 here, I’ve only been using it as an example because of clocks. We can just as well speak of congruence modulo 10, or 2, or 69, or 1268891587. In general, the number that we divide by to take the remainder is called the modulus.

And in fact, there’s nothing special about addition. Multiplication works the same way. Say we have two mid-size numbers, maybe 32 and 35, and we want to know the remainder of their product when we divide it by 12. 32×35=1120, and dividing that by 12 sounds like a pain. But if we first reduce mod 12, we have 32 = 8 mod 12, and 35 = 11 mod 12. Then 8×11 = 88, and if you know your multiplication tables you’ll know that 12×7 = 84. Therefore 88 = 4 mod 12, and I claim that 1120 = 4 mod 12 as well. Indeed, 12×93 = 1116, and 1120 = 1116+4, just as we wanted.

As another example, taking a modulus of 7, say we want to find the remainder of 848 × 197=167056. We could divide that by 7, or we could first reduce mod 7. Recall that 7×12 = 84, so 7×120 = 840, and 7×121 = 847. That means 848 = 1 mod 7. We can also see that 7×30=210, and 210-197 = 13. That means 7×28 = 196, so 197 = 1 mod 7 as well. 1×1=1, so 167056 = 1 mod 7. And indeed, if we were to long divide, we could see that 7×23865 = 167055.

And speaking of 7, something very interesting happens when your modulus is prime: namely, everything gets a multiplicative inverse. Remember that 0+a = a for any a, and similarly 1×a = a for any a. It turns out that if your modulus p is prime, anything from 1 up to p has a corresponding number that multiplies to 1. For instance, mod 7, we have

Which gives us all of the requisite background to start figuring out some divisibility tricks.

Now I’ll go over the method to identify multiples of a prime number p. The big idea we’re going to use is to take a large number and convert it into a smaller one that has, if not the same remainder mod p, at least either stays zero or stays nonzero. We should turn multiples of p into multiples of p, and turn non-multiples of p into non-multiples of p.

Our first step is to find an inverse for 10, mod p. That is, a number k such that 10k = 1 mod p. Recall that what this means is for 10k to be one more than a multiple of p; 10k = pq+1, or equivalently, 10k-1 = pq. We want some multiple of p to be one less than a multiple of 10, which means ending with a 9. Once we have that, we can add one to get a multiple of 10, and chop off the zero at the end to find k.

Now to use k, we just multiply it by n. If n is a multiple of p, then is is k×n. Since n = 0 mod p, k×n = k×0 = 0 mod p as well. But if n isn’t a multiple of p, then neither is k×n. Since p is prime, the only way k×n could be a multiple of p would be if either k or n were multiples of p. We know n isn’t a multiple of p in this case, and if k were a multiple of p, then so would 10k. But we already know that 10k isn’t a multiple of p; it’s one more than a multiple of p.

So great, multiplying by k either keeps n a multiple of p or a non-multiple of p, but what good does that do us? We said we wanted a smaller number than n, multiplying it by k will make it bigger. To deal with that, we’re going to split our number into digits. The last digit of a number is just its remainder mod 10: we can write n = 10a+b, where b is the remainder and a is the “rest” of the number. For example, 9645 = 10×964 + 5. 5 is the last digit, 964 is the “rest” of the number. If we write n = 10a+b, then

But recall the defining feature of k: that k×10 = 1 mod p. So k×n = 10×k×a + k×b = a + k×b mod p. In stark contrast to multiplying by k, we’ve divided most of the number by 10.

In general, a+k×b should be smaller than n, but it won’t always be. If k×b is very large then it might actually get bigger, but especially for very large numbers, ones that might have ten or twelve digits, this will certainly cut them down a bit. We’ll use this framework now to find divisibility tricks for a few different prime numbers, and also show off some more advanced techniques as appropriate.

We start off by finding an inverse for 10, mod 13, which means finding a multiple of 13 that ends in 9. 3×13=39 will do the trick, which means 4×10 = 1 mod 13, so our inverse is 4. So we then have 4×(10a + b) = a + 4b mod 13, and our trick is to take the last digit of the number, multiply it by 4, and add it on to the rest. Let’s try it: 1729 = 13×133, so we should end up with a multiple of 13.

It works! You might even be able to stop early and notice that 52 = 4×13 since it’s the number of cards in a standard deck of cards. Just to be safe, let’s try it again but where we expect a negative result. 13×103=1339, so 1337 isn’t a multiple of 13:

And 20 is obviously not a multiple of 13, so we correctly conclude that 1337 isn’t a multiple of 13. Now it’ll get a bit more interesting

Again, first we want an inverse for 10. 17×7 = 119, so 120 = 10×12 = 1 mod 17, so our inverse is 12. That means 12(10a+b) = a+12b mod 17, so our trick is to add 12 times the last digit to the rest of the number. We’ll try that on 17×196 = 3332:

This is a little inconvenient. Of course, we just found that 17×7 = 119 as part of deriving this rule, so we do know that it’s a multiple of 17, but that’s kind of a fluke unless you know your 17 times tables. This is a problem that sometimes shows up when our inverses of 10 are too big; sometimes we get stuck in loops with large-ish numbers, and the only way out is to do ordinary division or just know multiples.

But sometimes we can also modify the trick a little bit. Our inverse is 12, which is between 0 and 17, which seems like it’s as small as it could be. But then, 12 is somewhat close to 17; 12=17-5. Which also means -5 = 17×-1 + 12. So 12 = -5 mod 17. What this means is that, mod 17, taking a+12b is exactly the same as a-5b. This will generally make numbers smaller faster, and hopefully won’t give us such an inconvenient loop. Let’s try it with 3332:

We don’t need to do any work to see that 17 is a multiple of 17, so we’re done. Since these two tricks are the same mod 17, we can even mix and match: watch with the non-multiple of 17 9065:

At 881, we could have kept going with the subtraction trick, which would give us 88-5 = 83, and 8-15=-7 which is not a multiple of 17. But instead, we notice that 88 is 12 away from 100, so if we do the first trick we get straight to 100. No matter which trick we use at this point, when we multiply the last digit by something we get 0, so we can just pull 0 off the end until we get 1, which is also not a multiple of 17.

11 is a little bit more interesting: in order to get it one less than a multiple of 10, we need to go all the way to 11×9 = 99. As such 10 is the inverse of 10 mod 11, so 10(10a+b) = a+10b mod 11, and our trick is to add 10 times the last digit to the rest of the number. We’ll try that on 11×169=1859

And 77 is an obvious multiple of 11. Conversely, if we try it on 11×196–1= 2155,

Which is obviously not a multiple of 11. We could also borrow the new technique from 17, leveraging the fact that 10 = -1 mod 11, and subtract the last digit rather than adding ten times it. Doing that for 1859 and 2155

Which is neat, it does make our numbers smaller faster, but there’s still another way we can really blow it out of the water. Say instead of splitting our number into 10a+b to extract the last digit, we did 100a+b, extracting the last two digits. Then if we can find an inverse k for 100 mod 11, we can do almost the same thing. In fact, 100 = 1 mod 11, so 100a+b = a+b mod 11. As such, we can add the last two digits of the number to the rest. We’ll try it out with 1859 and 2155 as before:

And we have our answers in one fell swoop. In general, since we’re chopping off two digits per step rather than just one, this method will take about half as many steps to resolve. For a very large multiple of 11 like 18467885738786, the one-digit method will reduce it to 11 in twelve steps, the two-digit method only takes six. You can do something like this for any modulus indeed: if you find a multiple of p that ends in 99, that gives you an inverse of 100 mod p, and you can pull out two digits at once. Then, once the number is small enough, you can switch to the one-digit method.

At first, we can note that 23×3 = 69, so 7 is an inverse of 10 mod 23. But also 23×13 = 299, which means 3 is an inverse of 100 mod 23. Therefore our two tricks are to add 7 times the last digit to the rest, or 3 times the last two digits to the rest. Here, we’ll use these tricks in tandem to show that 6,436,346 is not a multiple of 23:

If we had stayed with the two-digit trick after 648, we’d have gone to 150, 151, 154, 153, 190, 271, 215, before finally landing on 47, but by switching to one digit at a time, we get there much faster. Teamwork makes the dream work, as they say.

Dear reader, there is so much more to say about modular arithmetic. There’s even a ton more to say about divisibility tricks. I’ve included a few possible extension exercises for those interested, but they’re purely optional.

1. Our recipe for a divisibility trick hinged on the fact that we could split a number into its last digit and “rest,” as 10a+b. If we wrote numbers in another base, say in binary, base 12, 20, 60, or anything else, what kinds of divisibility tricks would exist? What bases have the nicest divisibility tricks?

2. I only wrote about divisibility tests for primes, but you can do it with composite numbers as well. Try and figure out for what moduli you can use this inverse trick, and when it doesn’t work, how you can come up with tricks for those moduli as well.

3. These tricks are nice in that they’re generally easier than long division, especially for large moduli. Computers can do computation incredibly quickly though, including division, so it seems like they could have limited use for these kinds of tricks. That’s not quite true though. Explore what divisibility tests look like in binary, and consider how you might implement them in software, or indeed in hardware.

4. A major inconvenience with many of these tricks is that they can get stuck in loops, like 119 when checking divisibility by 17. But in most of the examples I gave this wasn’t an issue, and indeed that wasn’t intentional - these tricks tend not to get stuck in inconvenient loops in practice. Still though, try and investigate how likely it is that they get stuck, and whether using alternate tricks like different numbers of digits or subtracting rather than adding might help.

5. Write some code that generates a divisibility trick for any given prime. Or, for an extra challenge, combine this with problem 2 and have it generate a trick that checks for divisibility by any number in general. Try to have it determine whether the subtractive or additive version of a given trick is better, and how many digits is optimal.