Testing for Divisibility of ANY Number

Alex Nikic

Is the number 245 divisible by 5? Is 642 divisible by 2?

You may have already guessed yes. Pretty easy right? But what if I asked you, is 6,653,322 divisible by 3?

Not so easy anymore…

What if we wanted to know if any number is divisible by any other number, like if 4,863,685 is divisible by 445, quickly and efficiently – without a calculator? By the end of this article you have the tools to do exactly this – let’s get started!

Simplifying The Problem

Often in mathematics, it helps to simplify the problem. Instead of concerning ourselves with divisibility by any number, let’s first consider the easier question: how do you tell if a number is divisible by 2? Another useful problem solving technique in mathematics is to simply list out and try some examples. Essentially, if a number is divisible by 2, it must be in the 2 times table, so let’s start by listing the 2 times table:

2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50…

Notice a pattern yet?

The numbers in the 2 times table all have an ending digit of either 0, 2, 4, 6 or 8, whereas any other digit, such as 3 or 5, is not present in the last digit. Therefore we might say that a number is divisible by 2 if and only if its last digit is either 0, 2, 4, 6, or 8.

If instead we had the question: how do you tell if a number is divisible by 5, we could use the same method and try to find a pattern. Listing out the 5 times table:

5, 10, 15, 20, 25, 30, 35, 40, 45, 50…

Even simpler! Since numbers in the 5 times table can only end in 0 or 5, and no other digit, it seems that we can confidently say a number is divisible by 5 if and only if its ending digit is 0 or 5. In fact, the easiest example when considered this way is the 10 times table, as if a number ends in 0 it must be divisible by 10. 

Now we have some ideas how to tell if a number is divisible by 2, 5 and 10. Furthermore, if you think a little harder, you can also figure out if a number is divisible by 100, 1000, 10000, … and by extension, the numbers 20, 200, 2000, … and 50, 500, 5000 etc. Try it for yourself!

Now let’s try some other denominators, how would you know if a number is divisible by 4, for example? Again, let’s start by listing the multiples of 4:

4, 8, 12, 16, 20, 24, 28, 32, 36, 40, 44, 48, 52, 56, 60, 64, 68, 72, 76, 80, 84, 88, 92, 96, 100…

We can see here that these numbers all end in either 0, 2, 4, 6 or 8, however we cannot say that this is the condition for divisibility by 4. The number 26 ends in a 6, however, it cannot be divided by 4. In fact, in order to spot this particular pattern, you have to write out many more multiples of 4:

124, 128, 132, 136, …

200, 204, 208, 212, …

340, 344, 348, 352, …

Sometimes the listing strategy doesn’t quite allow you to easily spot a pattern, but if you look closely at the last two digits in each numbers above: 24, 28, 32, 36, 4, 8, 12, 40, 44, 48, 52 – they are all divisible by 4 themselves! So, we might hypothesise that for a number to be divisible by 4, the last two digits must be divisible by 4.

Proofs

We’ve done pretty well so far by just looking at examples, but as we’ve just seen with divisibility by 4, problems are arising. Our initial claim of divisibility by 4 under the condition of ending in a 0, 2, 4, 6 or 8 turned out to be untrue, even though it seemed convincing enough from the pattern. This is where mathematical proofs come in, and why they are so important. Proofs allow us to know for certain whether a fact is true or not, for any number, and may also allow us to discover things that listing multiples like above cannot achieve.

Let’s start with testing for divisibility by 2.

In our number system, every digit represents multiples of powers of 10. You might remember learning about place-value charts in primary school. For the number 134:

HundredsTensUnits
100304

134 = 100 + 30 + 4 = 1×100 + 3×10 + 4×1

Generalising this using some algebra, we can express any number in the form:

N = a + 10b + 100c + 1000d + …

It is important to note here that a, b, c, d, … must be whole numbers (integers) between 0 and 9, as that’s how our number system works. Each digit ranges from 0 to 9 in each place value.

Returning back to divisibility by 2, we can express a multiple of 2 as 2M, since we have that by definition any number multiplied by 2 is a multiple of 2. Therefore, at the end of our proof, we want to aim to have 2M appear should the number be divisible by 2. We start with our general number N:

N = a + 10b + 100c + 1000d + …

Using the fact that 10 = 2 x 5:

N = a + (2*5)b + (2*50)c + (2*500)d + …

Rearranging this:

N = a + 2(5b + 50c + 500d + …)

We can then simply define M as everything in the brackets (since it will still be a whole number) and so can write:

N = a + 2M

Analysing this last statement, this effectively means that any number can be expressed as a multiple of 2 plus some other number. Since an even number = even number + even number, and we know that 2M is clearly even, if therefore follows that N is even if and only if a is even. Additionally, since a represents the last digit of N, and is therefore between 0 and 9, a must either be 0, 2, 4, 6 or 8. Therefore a number is divisible by 2 if and only if its last digit is either 0, 2, 4, 6 or 8 – exactly as we stated earlier!

Likewise, a similar approach can be used for 5 and 10.

The proof for divisibility by 4 is a little different so let’s look at it in more detail:

N = a + 10b + 100c + 1000d + …

N = a + 10b + 4(25)c + 4(250)d + …

N = a + 10b + 4(25c + 250d +…)

N = a + 10b + 4M

Therefore for N to be divisible by 4, a + 10b must be divisible by 4 (since a multiple of 4 plus a multiple of 4 is itself a multiple of 4). Since a and b represent the last two digits of a number, this means that a number is divisible by 4 if and only if its last two digits are divisible by 4. Again, this is the same as we found earlier.

Using the ideas we’ve discussed above, try to complete the proof of divisibility by 8 for yourself. Here are the first few steps to get you started:

N = a + 10b + 100c + 1000d + 10000e + …

N = a + 10b + 100c + 8(125)d + 8(1250)e +…

We now have proofs for checking divisibility by quite a few numbers – 2, 4, 5, 8, 10 – but we are of course missing a pretty important one in the form of the number 3. Let’s start by listing out the multiples of 3 to try and find a pattern:

3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, 36, 39, 42, 45, 48, 51, 54, 57, 60, …

Unfortunately, we cannot look at the last digits here, as every digit from 0 to 9 is used. Can you spot anything else that might be useful? What about adding up all of the digits? It would seem that all of the digits of multiples of 3 sum to give a multiple of 3:

3 = 3

6 = 6

9 = 9

1 + 2 = 3

1 + 5 = 6

1 + 8 = 9

2 + 1 = 3

2 + 4 = 6

And so it seems that for a number to be a multiple of 3, its digits must sum to a multiple of 3. However, are you convinced that this would work for all numbers? Can you find a counterexample? I think it’s time for a proof.

N = a + 10b + 100c + 1000d + …

Using the fact that 10 = 9 + 1 (one more than a multiple of 3), and also that 100 = 99 + 1, 1000 = 999 + 1, etc:

N = a + (9+1)b + (99+1)c + (999+1)d + …

N = a + 9b + b + 99c + c + 999 d+ d +…

Collecting together the common factors:

N = a + b + c + d + … + 9b + 99c + 999d + …

N = a + b + c + d + … + 3(3b + 33c + 333d +…)

N = a + b + c + d + … + 3M

Therefore for N to be a multiple of 3, a+b+c+d+… must be a multiple of 3: meaning that the sum of the digits of a number must be a multiple of 3 for the number itself to be a multiple of 3. In the case that a+b+c+d+… is too large to see whether it is divisible by 3, you can always repeat this algorithm, looking at the sum of its digits instead. Additionally, a similar process to that used above can be used to prove divisibility by 9. Another chance for you to check your understanding by trying this one for yourself!

We can now finally answer one of the questions from the beginning of the article: is 6,653,322 divisible by 3?

Simply adding up the digits: 6 + 6 + 5 + 3 + 3 + 2 + 2 = 27, which is a multiple of 3, and therefore 6,653,322 is indeed divisible by 3. In fact:

6,653,322 ÷ 3 = 2,217,774

However, we still have a long way to go before finding out if any number is divisible by any other. There are many other tricks for divisibility by other specific numbers, like 11 for example, that we don’t have time to go into right now. If you are interested I suggest trying to find and prove them for yourself using the ideas we have discussed so far.

In order to prove divisibility for the general case of any number, we are going to need some more maths…

The Divisibility Algorithm

The Divisibility Algorithm allows us to find out whether a number is divisible by a number ending in 1, 3, 7, or 9. As the full explanation as to why this works is rather complicated, I will leave it until the end of the article for the interested reader. For now, we are just going to look at the key steps of how to use it in practice.

First, let M0 be the number you want to divide, and p be the number you wish to divide by. We want to find a value of k such that m = (kp+1)/10 is a whole number. In other words, we want to find a value of k such that kp+1 is a multiple of 10.

For example, if we want to test for divisibility by 3, we have m = (3k+1)/10 and we need to find a value of k that makes this a whole number, ie. which makes 3k+1 a multiple of 10. After a little thought, we can see this is satisfied when k = 3, as 3k + 1 = 3×3 + 1 = 10. Putting this into our formula this means that m = (3×3 + 1)/10 = 1. So for divisibility by 3, we take m = 1.

For a slightly harder example, if we wanted to test for divisibility by 17, we would have m = (17k+1)/10. To make 17k + 1 a multiple of 10 we can check increasing values of k as follows:

k = 1: 17×1 + 1 = 18

k = 2: 17×2 + 1 = 35

….

k = 7: 17×7 + 1 = 120

Therefore for divisibility by 17, we choose m = (17×4 + 1)/10 = 12.

Note, a quick way to find the k-values (and do check that you can calculate these for yourself) is as follows:

When p ends in 1: choose k = 9

When p ends in 3: choose k = 3

When p ends in 7: choose k = 7

When p ends in 9: choose k = 1

For p being even or a multiple of 5, there exists no value of k for which 2k+1 and 5k+1 respectively are multiples of 10. But, as we will see later, this isn’t too much of an issue as we have way around this.

For the next step in our algorithm we must write M0, the number we wish to divide by, as M0 = 10a1 + b1 (which can easily be done for any number). For our recursive step, we will write M1 = mb1 + a1 (where all of these numbers are now known – m comes from our calculations above and b1 and a1 from breaking up M0). From this result, we then repeat the process: 

M0 = 10a1 + b1 → M1 = mb1 + a1

M1 = 10a2 + b2 → M2 = mb2 + a3

Mn-1 = 10an + bn → Mn = mbn + an

Finally, if Mn is divisible by our desired number p, then M0 is also, and thus we will have answered our original question. Likewise if Mn is not divisible by our number, neither is M0, and thus our initial number is not divisible by the number in question.

This is of course quite complicated when using symbols and variables so let’s consider an example. Suppose we want to know if 1326 is divisible by 3. From our previous work, we must take m = 1. Performing the recursive algorithm, we have:

M0 = 1326 = 10a1 + b1 = 10 x 132 + 6, therefore a1 = 132, b1 = 6

So to calculate M1: M1 = mb1 + a1 = 1 x 6 + 132 = 138

M1 = 138 = 10a2 + b2 = 10 x 13 + 8, therefore a2 = 13, b2 = 8

So to calculate M2: M2 = mb2 + a2 = 1 x 8 + 13 = 21

M2 = 21 = 10a3 + b3 = 10×2 + 1, therefore a3 = 2, b3 = 1

So to calculate M3: M3 = mb3 + a3 = 1 x 1 + 2 = 3

Here we realise that M3 = 3, which is of course divisible by 3, and therefore M0 = 1326 is also divisible by 3! It is also perfectly acceptable to say that M2 = 21, which is divisible by 3, saving us the extra work of another recursion, as all we must do is reduce Mn down to a small number to spot whether it’s divisible by p or not.

This time, let’s say we want to know whether 1326 is divisible by 17. Using the previous calculated value for m, we will use m = 12:

M0 = 1326 = 10a1 + b1 = 10 x 132 + 6, therefore a1 = 132, b1 = 6

So to calculate M1 : M1 = mb1 + a1 = 12 x 6 + 132 = 204

M1 = 204 = 10a2 + b2 = 10 x 20 + 4, therefore a2 = 20, b2 = 4

So to calculate M2: M2 = mb2 + a2 = 12 x 4 + 20 = 68

M2 = 68 = 10a3 + b3 = 10 x 6 + 8, therefore a3 = 6, b3 = 8

So to calculate M3: M3 = mb3 + a3 = 12 x 8 + 6 = 102

M3 = 102 = 10a4 + b4 = 10 x 10 + 2, therefore a4 = 10, b4 = 2

So to calculate M4: M4 = mb4 + a4 = 12 x 2 + 10 = 34

Looking at M4, 34 is indeed divisible by 17, (34 ÷ 17 = 2), and therefore 1326 is divisible by 17.

Factorisation

Since the divisibility algorithm doesn’t work for even numbers and multiples of 5, we must use factorisation to factor out all the multiples of 2 and 5 from our starting number, and deal with them separately.

For example, if we were testing for divisibility by 48:

48 = 2 x 2 x 2 x 2 x 3 = 16 x 3

Therefore we only need to test for divisibility by 3 and 16. Our number must be divisible by both to also be divisible by 48. Testing for divisibility by 3 is not too difficult, but what about by 16?

Let’s try an example: is 408 divisible by 48?

Factorising out multiples of 2 and 5 from both:

Looking at both trees, we note that they both contain three 2s (their highest common factor is 2x2x2 = 8). This means that we can safely divide both by 2 three times, simplifying the question significantly.

Is 408 divisible by 48? → Is 51×8 divisible by 6×8? → Is 51 divisible by 6?

This question is much easier to answer: 51 is not divisible by 6. Therefore 408 is not divisible by 48.

Bringing It All Together

We can now finally answer our second question at the start: is 4,863,685 divisible by 445?

Factoring out multiples of 2 and 5: 445 = 5 x 89, therefore we need to test for divisibility by 5 and 89. Since 4,863,685 ends in a 5, it is divisible by 5.

Performing the divisibility algorithm for p = 89:

m = 89k + 110, choosing k = 1: m = (89×1 + 1)/10 → m = 9

M0 = 4,863,685 = 10a1 + b1 = 10 x 486,368 + 5, therefore a1 = 486,368, b1 = 5

So to calculate M1 : M1 = mb1 + a1 = 9 x 5 + 486,368 = 486,413

M1 = 486,413  = 10a2 + b2 = 10 x 48,641 + 3, therefore a2 = 48,641, b2 = 3

So to calculate M2 : M2 = mb2 + a2 = 9 x 3 + 48,641 = 48,668

M2 = 48,668 = 10a3 + b3 = 10 x 4866 + 8, therefore a3 = 4866, b3 = 8

So to calculate M3: M3 = mb3 + a3 = 9 x 8 + 4866 = 4938

M3 = 4938 = 10a4 + b4 = 10×493 + 8, therefore a4 = 493, b4 = 8

So to calculate M4: M4 = mb4 + a4 = 9 x 8 + 493 = 565

M4 = 565 = 10a5 + b5 = 10×56 + 5, therefore a5 = 56, b5 = 5

So to calculate M5: M5 = mb5 + a5 = 9 x 5 + 56 = 101

M5 = 101 = 10a6 + b6 = 10×10 + 1, therefore a6 = 10, b6 = 1

Therefore to calculate M6: M6 = mb6 + a6 = 9 x 1 + 10 = 19

As 19 is not divisible by 89, 4,863,685 is not divisible by 89

Using this approach, computers can work out the divisibility of enormous numbers – numbers so big that it would take too long to divide them using ‘normal methods’. Imagine trying to divide a million or billion digit long number by 3; it is considerably quicker to just add its digits up, and repeat this on the result to arrive at the answer much faster. It is techniques like these that mathematicians use in order to solve immensely large and difficult problems, contributing to new discoveries and technologies, advancing our knowledge and understanding of how everything in the world works.

To summarise, in order to find if a number is divisible by another, we must:

  • Factor out any multiples of 2 and 5 from the divisor
  • Cancel out any multiples of 2 and 5 from the number being divided if possible
  • Check for divisibility by the remaining factors using the division algorithm and previous tricks

Finally, here is a summary of the useful shortcuts and divisibility tricks we discussed earlier:

Divisibility by 2 – Ending digit is divisible by 2

Divisibility by 4 – Ending 2 digits are divisible by 4

Divisibility by 8 – Ending 3 digits are divisible by 8

Divisibility by 5 – Ending digit is either 0 or 5

Divisibility by 10 – Ending digit is 0

Divisibility by 100 – Ending 2 digits are 0

Divisibility by 3 – The sum of the digits are divisible by 3

Divisibility by 9 – The sum of the digits are divisible by 9

Explanation of the Divisibility Algorithm

We start by rewriting the steps of the algorithm with the explicit formula for m = (kp+1)/10

M0 = 10a1 + b1

M1 = mb1 + a1 = ((kp+1)/10)b1 + a1 = 10a2 + b2

M2 = mb2 + a2 = ((kp+1)/10)b2 + a2 = 10a3 + b3

….

Mn = mbn + an = ((kp+1)/10)bn + an

Next, we multiply the formula for M1 by 10:

M0 = 10a1 + b1

10M1 = (kp+1)b1 + 10a1

= kb1p + 10a1 + b1

= kb1p + M0

So now we have M1 in terms of the original number M0. Repeating this idea we next multiply M2 by 102 = 100:

100M2 = 10(kp+1)b2 + 100a2

= 10kb2p + 100a2 + 10b2

= 10kb2p + 10(10a2 + b2)

= 10kb2p + 10M1

= 10kb2p + kb1p + M0

= (kb1 + 10kb2)p + M0

This gives M2 in terms of the original M0. We continue in this way each Mk, where Mk is multiplied by 10k:

1000M3 = 100(kp+1)b3 + 1000a3

= 100kb3p + 100(10a3 + b3)

= 100kb3p + 100M2 

= 100kb3p + (kb1 + 10kb2)p + M0

= (kb1 + 10kb2 + 100kb3)p + M0

10nMn = (kb1 + 10kb2 + 100kb3 + … + 10n-1kbn)p + M0

10nMn = pA + M0

M0 = 10nMn – pA

So if 10nMn is divisible by p, M0 is divisible by p. Since p cannot be a multiple of 2 or 5, if 10nMn is divisible by p, Mn is divisible by p, and the opposite holds true (by Euclid’s Lemma).
Therefore, if p divides Mn, then p divides M0, and if p doesn’t divide Mn, p doesn’t divide M0.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s