Going back through my Leapfrog Division and Leapfrog Division II posts, it put me in mind of divisibility tests. If you don't remember, those are simply ways of checking whether a given number is evenly divisible by another number.

In school, they often teach simple rules for quickly identifying 2, 3, 4, 5, 6, 8, 9, and 10. 7 is usually skipped because it's a prime number, and the tests are more difficult to teach.

It turns out, however, that by using the quotient and remainder and neighboring numbers, similar to the way we used them in the Leapfrog Division posts, many prime numbers become much easier to test!

The use of neighboring numbers divisible by 10 makes these rules surprisingly easy to recall and use. Instead of starting with 9, which already has its own simple divisibility test, I'll start with 19. Very few people know how to test for divisibility by 19.

DIVISIBILITY BY 19: The trick is to divide a given number by 20 (19 + 1), so that you get a quotient and remainder. If the quotient and remainder add up to a multiple of 19, then the original number is divisible by 19!

For example, let's test whether 437 is evenly divisible by 19. 437 ÷ 20 = 21, with a remainder of 17. 21 + 17 = 38, and since 38 is a multiple of 19, we know that 437 must be a multiple of 19, too! If you're wondering, 437 = 19 × 23.

Why does using a neighboring number work for divisibility tests? Think of it this way: We're given an integer (whole number) x and we want to test whether it's evenly divisible by n, so we divide by another integer n + 1, to get 2 more integers, a quotient, q, and a remainder, r. Thus, the problems boil down to this format:

^x⁄_{(n + 1)} = q + r

To simplify the equation, we multiply both sides by (n + 1) to get:

x = (n + 1)(q + r)

Expanding the right side results in this:

x = nq + nr + q + r

Since every variable here represents an integer, we know that nq, nr, as well as the sum of nq and nr must all be evenly divisible by n. Therefore, if q + r equals a multiple of n, then x must be evenly divisible by n, as well! Conversely, if q + r doesn't equal a multiple of n, then x won't be evenly divisible by n.

GENERALIZING DIVISIBILITY TESTS: Since our only assumption in the above equations is that we're using integers, and that there's an easily divisible number, such as a multiple of 10, 1 greater than the number for which we're testing, this test works well for any number ending in 9, as long as you're comfortable dividing by the following multiple of 10!

So, to test for divisibility by 29, you could divide by 30, and add the resulting quotient and remainder. Is 377 evenly divisible by 29? Let's try: 377 ÷ 30 = 12 remainder 17, and 12 + 17 = 29, so 377 is definitely divisible by 29! How about 523? 523 ÷ 30 = 17 remainder 13, and 17 + 13 = 30, so 523 is not evenly divisible by 29.

HOW CLOSE ARE WE TO A MULTIPLE?: The 523 example does give us 30, which is only 1 more than 29. Does this mean that 523 is 1 greater than a multiple of 29? Let's test out 522 and find out. 522 ÷ 30 is 17 remainder 12, and 17 + 12 = 29, so 522 must be evenly divisible by 29! In fact, 522 = 29 × 18.

As long as you know your first few multiples of the number n for which you're testing, you can often use this test to see how close you are to a perfect multiple of n.

For our next example, let's test 1,418 for divisibility by 19. 1,418 ÷ 20 = 70 remainder 18, and 70 + 18 = 88. 88 isn't a multiple of 19, so 1,418 isn't evenly divisible by 19.

However, you should realize that 19 does have two multiples close to 88, which are 76 and 95. So, you could subtract 12 (76 - 88) or add 7 (95 - 88) to get to a multiple of 19! This quickly tells us that 1,406 (1,418 - 12) and 1,425 (1,418 + 7) are perfect multiples of 19.

HANDLING BIG RESULTS: What happens if you get a result that is so big that you're not familiar with whether the result is a multiple? For example, is 31,842 evenly divisible by 29? Let's run it through our test and find out.

31,842 ÷ 30 = 1,061 remainder 12, and 1,061 + 12 = 1,073. As long as 1,073 is evenly divisible by 29, then 31,842 is evenly divisible by 29. There's the problem: Is 1,073 evenly divisible by 29? We can run the test again to find out.

1,073 ÷ 30 = 35 remainder 23, and 35 + 23 = 58. Yes, 58 is easily recognizable as a multiple of 29, so we now know that 31,842 is evenly divisible by 29!

One of the best parts about testing again and again in this way is that it preserves the same remainder throughout the repeated tests. So, if I'd tested 31,845 instead (3 more than 31,842), it would result in 1,076 (3 more than 1,073) in the first test, and 61 in the second test (3 more than 58). So, even with repeated tests, I can still determine how close a given number is to a perfect multiple!

TESTING NUMBERS NOT ENDING IN 9: Having just talked about the importance of knowing the first few multiples, you'd probably think it's unusual if I wanted to test, say, the number 91 for divisibility by 39. After all, just counting 39...78...117, we can already see that 91 isn't a multiple of 39. Let's run through the test anyway.

For 39, we'll divide by 40 and look at the quotient and remainder. 91 ÷ 40 = 2 remainder 11, and 2 + 11 = 13. Since 13 isn't a multiple of 39, we verified that 91 isn't a perfect multiple of 39, just like we expected. We can also say that 91 is 13 more than a multiple of 39, as discussed in the previous section.

But wait a minute, 13 may not be a multiple of 39, but 39 is a multiple of 13! If 91 is 13 beyond a multiple of 39, it must also be 13 beyond a multiple of 13! In other words, we can use our test for 39 not only for 39, but for divisibility by 13, as well!

When testing for divisibility by any number n with this approach, you can also use it as a test for factors of n! We could also use this approach to test for divisibility by 3, since 3 is a factor of 39, but 3 already has a much easier divisibility test, so this is overkill.

As I mentioned earlier, teachers often skip teaching divisibility by 7, but you should already see how to test for divisibility by 7 with this method. Since 7 is a factor of 49, we can divide by 50 (49 + 1) to test for division by 7!

Is 1,585 evenly divisible by 7? Checking, we see that 1,585 ÷ 50 = 31 remainder 35, and 31 + 35 = 66. You should know your multiples of 7 well enough to recognize that 66 isn't a multiple of 7, so 1,585 isn't evenly divisible by 7.

We also know, of course, that 66 is only 3 more than a multiple of 7, so 1,585 must be 3 more than a multiple of 7, too!

FINAL THOUGHTS: Think about the power of this style of divisibility testing:

• You can quickly recall the test for divisibility of any number ending in 9.
• You can use this test to find how close you are to a perfect multiple.
• If you're not sure of your results, you can repeat the test and still know how close you are to a perfect multiple.
• You can test for almost any odd number, by scaling it up so it ends in 9.