Math - Divisibility of Numbers

Recently, I saw this video by Michael "DONG" Vsauce about divisibility rules for certain numbers and why they work. The bulk of his video talked about the digits 1-9. I'd seen videos like this before, on YouTube and I think in a lecture on Great Courses. He ended the main portion of his video by noting that, no, it's not faster to do this kind of thing; figuring out these divisibility rules is still slower than any calculator; however, it is fun, and helps us get to know numbers, and math in general, better.

So then I started thinking about divisibility myself. Specifically, I wanted to look at prime numbers larger than 10. It's easy enough for something like is n divisible 15, since "does n have a 0 or 5 at the end?" accounts for 5, and an easy divisibility check accounts for 3 (adding up the digits and seeing if that number is divisible by three). If both of those of those check out, then it is divisible by 15.

But what about 13? 17? These prime numbers can't be broken into easier checks. I wouldn't be able to tell at a glance in most cases if some random string of 2 or 3 digits is divisible by 17.

So in trying to come up with a divisibility rule, I broke down the justification for the others. Let's look at the equation here:

abc = 100a + 10b + c

abc being a three digit number, like 351. How could I determine if it's divisible by 3? There's two ways. First, there's the easy way of adding up the digits: 3 + 5 + 1 = 9, and so it is divisible. In fact, 351 = 3 * 117. The second way is basically the same, but goes through a few extra steps. First, we restate the previous equation like this:

abc = 99a + a + 9b + b + c

abc = (99a + 9b) + (a + b + c)

We know intuitively that 3 goes into both 99 and 9, so we then know that it divides 99a and 9a. Does it divide a + b + c? We can take those digits and apply the method we used above.

But we can also apply this technique to large prime numbers as well. Let's try 17. First, we split it into the two sections. What's the largest multiple of 17 less than 100? We'll restate 100a as 85a + 15a, like so:

abc = (85a) + (15a + 10b + c)

In this case, we don't get a simple version like with 3. 17 only goes into 100, and not 10 or 1. However, it is a tiny bit simpler. We know that 17 divides 85, so we also know that it divides 85a. Does it divide the latter part? Let's use 351 as an example.

15(3) + 10(5) + 1

15 + 50 + 1 = 66

A quick check of 85 - 17 = 68 shows that 17 does not divide 66. Therefore, it should not divide 351. And, a quick check on a calculator shows that 351/17 = 20.647058823529412, and is thus not evenly divisible.

This is a naive approach, since easier methods for 1-10 are well-known, and I'm sure most prime numbers between 10-100 already have easier methods. But it was fun to use the logic for numbers 1-10, and apply it to others myself, even if I didn't come up with a crazy new method of figuring out divisibility.