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:

Hundreds	Tens	Units
100	30	4

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 M₀ 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 M₀, the number we wish to divide by, as M₀ = 10a₁ + b₁ (which can easily be done for any number). For our recursive step, we will write M₁ = mb₁ + a₁ (where all of these numbers are now known – m comes from our calculations above and b₁ and a₁ from breaking up M₀). From this result, we then repeat the process: 

M₀ = 10a₁ + b₁ → M₁ = mb₁ + a₁

M₁ = 10a₂ + b₂ → M₂ = mb₂ + a₃

…

M_n-1 = 10a_n + b_n → M_n = mb_n + a_n

Finally, if M_n is divisible by our desired number p, then M₀ is also, and thus we will have answered our original question. Likewise if M_n is not divisible by our number, neither is M₀, 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:

M₀ = 1326 = 10a₁ + b₁ = 10 x 132 + 6, therefore a₁ = 132, b₁ = 6

So to calculate M₁: M₁ = mb₁ + a₁ = 1 x 6 + 132 = 138

M₁ = 138 = 10a₂ + b₂ = 10 x 13 + 8, therefore a₂ = 13, b₂ = 8

So to calculate M₂: M₂ = mb₂ + a₂ = 1 x 8 + 13 = 21

M₂ = 21 = 10a₃ + b₃ = 10×2 + 1, therefore a₃ = 2, b₃ = 1

So to calculate M₃: M₃ = mb₃ + a₃ = 1 x 1 + 2 = 3

Here we realise that M₃ = 3, which is of course divisible by 3, and therefore M₀ = 1326 is also divisible by 3! It is also perfectly acceptable to say that M₂ = 21, which is divisible by 3, saving us the extra work of another recursion, as all we must do is reduce M_n 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:

M₀ = 1326 = 10a₁ + b₁ = 10 x 132 + 6, therefore a₁ = 132, b₁ = 6

So to calculate M₁ : M₁ = mb₁ + a₁ = 12 x 6 + 132 = 204

M₁ = 204 = 10a₂ + b₂ = 10 x 20 + 4, therefore a₂ = 20, b₂ = 4

So to calculate M₂: M₂ = mb₂ + a₂ = 12 x 4 + 20 = 68

M₂ = 68 = 10a₃ + b₃ = 10 x 6 + 8, therefore a₃ = 6, b₃ = 8

So to calculate M₃: M₃ = mb₃ + a₃ = 12 x 8 + 6 = 102

M₃ = 102 = 10a₄ + b₄ = 10 x 10 + 2, therefore a₄ = 10, b₄ = 2

So to calculate M₄: M₄ = mb₄ + a₄ = 12 x 2 + 10 = 34

Looking at M₄, 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

M₀ = 4,863,685 = 10a₁ + b₁ = 10 x 486,368 + 5, therefore a₁ = 486,368, b₁ = 5

So to calculate M₁ : M₁ = mb₁ + a₁ = 9 x 5 + 486,368 = 486,413

M₁ = 486,413  = 10a₂ + b₂ = 10 x 48,641 + 3, therefore a₂ = 48,641, b₂ = 3

So to calculate M₂ : M₂ = mb₂ + a₂ = 9 x 3 + 48,641 = 48,668

M₂ = 48,668 = 10a₃ + b₃ = 10 x 4866 + 8, therefore a₃ = 4866, b₃ = 8

So to calculate M₃: M₃ = mb₃ + a₃ = 9 x 8 + 4866 = 4938

M₃ = 4938 = 10a₄ + b₄ = 10×493 + 8, therefore a₄ = 493, b₄ = 8

So to calculate M₄: M₄ = mb₄ + a₄ = 9 x 8 + 493 = 565

M₄ = 565 = 10a₅ + b₅ = 10×56 + 5, therefore a₅ = 56, b₅ = 5

So to calculate M₅: M₅ = mb₅ + a₅ = 9 x 5 + 56 = 101

M₅ = 101 = 10a₆ + b₆ = 10×10 + 1, therefore a₆ = 10, b₆ = 1

Therefore to calculate M₆: M₆ = mb₆ + a₆ = 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

M₀ = 10a₁ + b₁

M₁ = mb₁ + a₁ = ((kp+1)/10)b₁ + a₁ = 10a₂ + b₂

M₂ = mb₂ + a₂ = ((kp+1)/10)b₂ + a₂ = 10a₃ + b₃

….

M_n = mb_n + a_n = ((kp+1)/10)b_n + a_n

Next, we multiply the formula for M₁ by 10:

M₀ = 10a₁ + b₁

10M₁ = (kp+1)b₁ + 10a₁

= kb₁p + 10a₁ + b₁

= kb₁p + M₀

So now we have M₁ in terms of the original number M₀. Repeating this idea we next multiply M₂ by 10² = 100:

100M₂ = 10(kp+1)b₂ + 100a₂

= 10kb₂p + 100a₂ + 10b₂

= 10kb₂p + 10(10a₂ + b₂)

= 10kb₂p + 10M₁

= 10kb₂p + kb₁p + M₀

= (kb₁ + 10kb₂)p + M₀

This gives M₂ in terms of the original M₀. We continue in this way each M_k, where M_k is multiplied by 10^k:

1000M₃ = 100(kp+1)b₃ + 1000a₃

= 100kb₃p + 100(10a₃ + b₃)

= 100kb₃p + 100M₂ 

= 100kb₃p + (kb₁ + 10kb₂)p + M₀

= (kb₁ + 10kb₂ + 100kb₃)p + M₀

…

10ⁿM_n = (kb₁ + 10kb₂ + 100kb₃ + … + 10^n-1kb_n)p + M₀

10ⁿM_n = pA + M₀

M₀ = 10ⁿM_n – pA

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