Divisibility Rules - An Explanation

How much time would you need to check if a given number is divisible by 2 –15 without a computer? Well, for the first few numbers, you would be so fast. But you will get stuck at 7 or 13 right? Don’t worry. After reading this article, you won’t. Give it a try.

Table Of Contents

  1. "The Obvious Technique"
  2. Elementary Rules
  3. The Unknown Rules

First of all, for those who don't know,

A divisibility rule is a shorthand way of determining whether a given integer is divisible by a fixed divisor without performing the division, usually by examining its digits.
Wikipedia(@)

That being said, we are good to go.

#"The Obvious Technique"

Before diving into the number-specific rules, I would like to explain to you an obvious technique, that can be done for any number. (I am almost sure that you know about this technique. But I am going to explain it anyway.)

Let’s say that we want to check if p is divisible by q. The divisibility of p by q is conserved if we add or subtract a multiple of q to or from p. We can use this rule to reduce the big numbers into small ones which makes it easy for us to check if they are divisible.

Checking if 3056 is divisible by 27

For example, let’s say that we want to check if 3056 is divisible by 27. We can do that using the above-mentioned technique. I will subtract 2700 and then 297 (which are both divisible by 27), from 3056.

As it comes down to 69, which is not divisible by 27, 3056 is also not divisible by 27.

It can be long and hard most of the time. But in some cases, it can be easy and fast (for example, checking if 5430 is divisible by 27). We will use this process in some (if not all) rules in this story. I will refer to this technique as the Basic Technique in this story.

Note: iff means if and only if, for example, A iff B means, A is true if and only if B is true.

Also, note that I am talking about divisibility rules in the “Decimal Number System”. You can find divisibility rules in other number systems with the ideas gathered from here. If you think of yourself as a nerd, try to find divisibility rules in binary and octal number systems.

#Elementary Rules

Before we dive into the main rules, I want to explain some of the elementary rules that everyone knows. These are sorted from easy to hard.

#10

Check if the last number is 0. I know that I shouldn’t include it here. But whatever. And as it is so obvious, let’s move on.

#2, 5 (n)

Check if the last digit is divisible by n. I would like to explain why. You can skip the next paragraph if you want.

Take a number in the format of ABC (where 0 ≤ A, B, C ≤ 9) (It doesn’t have to be a 3-digit number; it can any number of digits).

Everyone knows that ABC can be written as AB0 + 00C. We know that AB0 is divisible by 2, 5, 10 (because the last digit is 0). As mentioned in the Basic Technique, 00C’s divisibility of 2 is the same as ABC’s. So checking the last digit is enough.

I also want to say that 2, 5, 10 are the only numbers that have the “check the last digit” divisibility-rule type.

#3, 9 (n)

These two are also easy, but you can’t tell it instantly like 2 or 5. Add up the digits of the number, and see if it is divisible by n. These are the only numbers that have the “add up the digits to check” divisibility-rule type.

For example, 12049’s digits add up to 16. So 12049 is not divisible by both 3 and 9 as 16 is not divisible by both 3 and 9.

#4, 8

4 and 8’s divisibility rules are like 2's. But instead of checking the last digit, you have to check the last 2 digits for 4 and check the last 3 digits for 8.

#6

A number is divisible by 6 iff the number is divisible by both 2 and 3. So do the rules for 2 and 3 on the number, and if both ended up true, then the number is divisible by 6.

#The Unknown Rules

As you are clear about the basic rules for divisibility testing, we can start looking at some lesser known rules.

I am not going to explain the general cases anymore. Because it would be so hard for both you and me. I will just explain with an example.

#7, 11, 13, 17 (n)

These numbers share the same kind of pattern in their divisibility rules, so I grouped them.

I am going to show you how to check if 54012 is divisible by 7. First, observe this example. Then choose a different number and see if you really understood it.

Checking if 54012 is divisible by 7

54012, so the last number is 2 and the other numbers are 5401. So I am going to subtract 4 (2 times the last number) from 5401, and I get 5397. As I am not sure if it is divisible by 7, I am going to do it again. I am repeating this process until I get 41 which I know is not divisible by 7. So we can conclude that 54012 is not divisible by 7.

I will refer to this technique as “Recursive Technique”.

To check if a number is divisible by 11 or 13 or 17, you have to follow the same process. For 7, we multiplied the last digit by 2. For other numbers, have to multiply it with a different number, based on the below table.

nmultiply with
72
111
139
175

We will see why these specific numbers are used.

#For all the other numbers

This may sound stupid to you. But wait, I am not saying that every single number has ONE simple divisibility rule. I am just saying that there are some techniques that you can use to find a number’s divisibility rule.

First, you have to see if it is a power of 2 or 5. Let’s say that the number is nth power of 2 or 5. Then check for the last n digits. That’s enough. This is why I told you to check for the last 2 digits for 4 (2²) and 3 digits for 8 (2³). The explanation for this is quite easy. 10 is divisible by 2 and 5, so 10’s nth power is divisible by the nth power of both 2 and 5. I hope you can finish the explanation on your own. [Refer to the 2, 5’s explanation] Don’t be sad if it is not a power of 2 or 5, we have more techniques.

Next, Check if any of its multiples have 1 as the last digit. For example, 7 has 21, 9 has 81, 11 has 11, 13 has 91, 17 has 51, and so on. If it does, you can do the Recursive Technique. But you have to multiply the last digit with a number. How do you select the number? I hope the table below gives you an idea.

nmultiply with
7212
11111
13919
17515

You have to multiply by the number you get after crossing out the last “1”. But why?, we are just doing the Basic Technique. Think about it.

And I have one more trick which works for non-primes. Let’s say we want to check if p is divisible by q. We can do that by checking if p is divisible by all (or some) of the factors of q. In most cases, it can be hard to do, but sometimes it can be helpful.

For example, 6, we check for its factors (2, 3). It’s so easy in the case of 6 because we have to check for only 2 and 3. But what about other numbers that have many factors? For those numbers, there is an easy way too. Instead of checking for all of the factors of q, you can just check it for 2 numbers. But how would you select those two numbers? Those two numbers must fulfil these 2 conditions.

  1. Their greatest common divisor (GCD) is 1.
  2. when multiplied, they give q.

With these tricks and techniques, you can check if a number is divisible by any number between 2 and 28 in 10 seconds. You can go for other numbers too, but it may take longer. But as you use them again and again, you will slowly become fast.

PS: The Basic Technique and the Recursive Technique are not mathematical terms. I am just naming them just for the sake of reference.