Ken Ward's Mathematics Pages
Number Theory Divisibility Tests
Number Theory Contents
See also Tables of CoefficientsPage Contents
Divisibility Tests
In Medieval times and before, there was a great use of tests to check calculations.Arithmetic calculations by hand (and sometimes by machine) often go awry, and checking is important. Nowadays, these checks are less common, due to faith in the electronic computer and calculators. When, however, we do checks, we tend to repeat our calculations, which might leads us to repeat the error; consequently, repeated checks might continue to produce the same error. The divisibility tests enable us to check our calculations in a different way, therefore avoiding repeating our mistakes. Of course, divisibility tests can also be used to find factors, etc...
On this page, I write about what I call the traditional or conventional method (for want of a name!) of divisibility checks, and on another page a method called Method 2.
Intuitive Approach
In the days when a computer meant "one who computes" and referred to a person who did arithmetic, there was a demand for tests to determine the accuracy of the arithmetic (pencil and paper arithmetic is notoriously subject to error!). Many of these tests have a long history, going back to Medieval times and even hundreds or thousands of years before.To take a simpler example. Suppose we have multiplied a number by 7 and we have 378. To check the arithmetic, we can begin by subtracting 7 from the number (if we subtract a multiple of 7 from the number, what remains must also be divisible by 7, if the number is so divisible).
We keep the remainder (371) and look at more of the number. Clearly 70 is divisible by 7, so we can simplify further by subtracting 70, leaving 301
In the remainder so far, we have 301, and 3·7=21, so we can subtract 21, getting 280. Discarding the 0, we have 28 remaining, and as this is divisible by 7, so is the number 378, confirming our calculations.
Alternatively, with 378, we could note that 4x7=28, and we can subtract this from 378, leaving 350. Dropping the 0, we note that 7x5=35, so the number, 378, is divisible by 7.
General Principle
We can represent integers (up to 99999), where a, b, c, d, and e are 0, 1, 2, ... 9 and N is a nonnegative integer, as follows
[1.1](Naturally, larger numbers can be represented in a similar manner)
We can write out abcde as follows:
[1.2]If N is divisible by a whole number n, then [1.2] is divisible by n. That is, the right-hand side, mod n, is zero, if N is divisible by n.
Taking the example of dividing by 7, [1.2] (with some terms dropped for clarity) can be written:
[1.3]If the number, N, is divisible by 7, the multiples of 7 can be dropped (because they are 0, mod 7, and because they are divisible by 7, so they need not be taken into account). The remainder is:
[1.4]That is, we can say that if N is divisible by 7, then [1.4] must be divisible by 7. Also, if [1.4] is divisible by 7, then N is divisible by 7 because [1.4] is the remainder on dividing [1.3] by 7.
We can write a longer version of [1.3]:
[1.5]Here the coefficients are 1, 3, 2, 6, 4, 5....
The same number can be expressed as follows (with the coefficients negative smaller numbers:
[1.6]In this case, the formula becomes easier to remember and simpler to use, with the coefficients 1, 3, 2, -1, -2, -3:
[1.7]Naturally, the negative numbers are the complements of the positive ones they replace.
Divisibility by 2
Seeking the rule
We first form a table, beginning with the units and continuing to the tens, hundreds, etc.., as follows:| Powers of 10 | Mod 2 |
| 1 | 1 |
| 10 | 0 |
| 100 | 0 |
| 1000 | 0 |
From the table we can make a formula by substituting in 1.2 the Mod 2 values for the various powers of 10. In this case all the coefficients (powers of 10 mod 2) are zero, except the last number:
[1.3]So a number is divisible by 2, if the last digit is. In other words, it is divisible by 2 if it is an even number.
Divisibility by 3
In order to find the coefficients of a formula, we make a table for 3:| Powers of 10 | Mod 3 |
| 1 | 1 |
| 10 | 1 |
| 100 | 1 |
| 1000 | 1 |
In this case, when we substitute the values of Mod 3 from the table into 1.2, all the coefficients of our formula for 3 are 1:
[1]Which means that
if the sum of its digits are divisible by 3, then so is the number.
For instance, we know 762 is divisible by 3 because
7+6+2=15, is divisible by 3
(or 15 gives 1+5=6, which is divisible by 3).
Divisibility by 4
The table of coefficients for 4 follows:| Power of 10 | Mod 4 |
| 1 | 1 |
| 10 | 2 |
| 100 | 0 |
| 1000 | 0 |
The rule is:
add the units digit to twice the tens digit, and if the result is divisible by 4, then so is the number (ignore any other digits).
For example:
756 gives 2·5+6=16, which is divisible by 4 (Ignore the 7).
The common-sense rule (the rule often stated, but based on different principles from this one) is that a number is divisible by 4
If the last two digits are divisible by 4
This is because 100 and higher numbers are divisible by 4 if the last 2 digits are so divisible.
divisibility by 5
The table of coefficients for 5 is:| Power of 10 | Mod 5 |
| 1 | 1 |
| 10 | 0 |
| 100 | 0 |
| 1000 | 0 |
After the units, the coefficients are zero, so if the units figure is divisible by 5, then so is the number.
In other words,
A number is divisible by 5 if it ends in 5 or 0
divisibility by 6
The table of coefficients for 6 is:| Power of 10 | Mod 6 |
| 1 | 1 |
| 10 | 4 |
| 100 | 4 |
| 1000 | 4 |
The coefficient for the units figure is 1, and all the rest are 4.
The rule is therefore,
add the units figure to 4 times the rest of the number, and if this is divisible by 6, then so is the number.
The alternative rule is
Subtract from the units figure twice the rest of the number
Example:
Is 384 divisible by 6?First Rule:
384 gives 4+4·38=76
76 gives 6+4·6=30
30 gives 0+4·3=12
12 gives 2+4·1=6
Second Rule:
384 gives 4-(2·38)=72
72 gives 2-(2·7)=12
12 gives 2-(2·1)=0
It seems that it is often easier to check whether the number is even and whether it divides by 3!
divisibility by 7
The table of coefficients follows:| Power of 10 | Mod 7 | Mod 7, alternative |
| 1 | 1 | 1 |
| 10 | 3 | 3 |
| 100 | 2 | 2 |
| 1000 | 6 | -1 |
| 10000 | 4 | -3 |
| 100000 | 5 | -2 |
| 1000000 | 1 | 1 |
| 10000000 | 3 | 3 |
| 100000000 | 2 | 2 |
| 1000000000 | 6 | -1 |
| 10000000000 | 4 | -3 |
In the first formula, we make a sum by multiplying the units, tens, hundreds., digits by respectively 1, 3, 2. That is, substituting the Mod 7 values for the powers of 10 in Equation 1.2. We then multiply the thousands, ten-thousands and hundred-thousands digits by 6, 4, 5, respectively and repeat these sequences, as necessary
[3.1]The second formula uses the "alternative" numbers, and is easier to remember: the sequences being 1, 3, 2, followed by -1, -3, -2 and the sequences repeat at the millions digit.
[3.2]The patterns repeat. The pattern for Equation 3.2 is particularly easy, being 1, 3, 2 followed by the negatives: -1, -3, -2, and this pattern repeats.
Example (using 3.1)
861 gives 1+3·6+2·8=35.
35 gives 5+3·3=14.
14 gives 4+3·1=7
Example 2:
861861 gives 1+3·6+2·8-1-(3·6)-(2·8)=0, which is divisible by 7!
Example 3
1771938 gives 8+9+18-1-21-14+1=0, hence divisible by 7.
This formula has received a bad press, and in the using, it is probably, in general, superior to the corresponding one from Method 2.
For example, using 147:
Method 2:
147 gives 14-2·7=0, so it divides by 7
Method 1:
147 gives 7+3·4+2·1=21.
21 gives 1+3·2=7
The Method 2 seems easier, but...
Method 2:
117649 gives 11764-2·9=11746.
11746 gives 1174-2·6=1162.
1162 gives 116-2·2=112.
112 gives 11-2·2=7
Method 1:
117649 gives 9+(3·4)+(2·6)-(7·3)-(1·2)+1=21.
21 gives 1+3·2=7
With even larger numbers, the Method 1 seems even more superior to the apparently easy-looking Method 2.
For instance, is
311973482284542371301330321821976049
divisible by 7? While the number is hard to check, and too big for a calculator or normal computer range, using Method 1 as a check is much more efficient.
divisibility by 8
Consulting the table below, we note that the rule for 8 is:Add the units figure to twice the tens figure and add four times the 100's figure.
Note that the rule is a continuation of the rule for divisibility by 4 (add the units digit to twice the tens digit).
| Power of 10 | Mod 8 |
| 1 | 1 |
| 10 | 2 |
| 100 | 4 |
| 1000 | 0 |
| 10000 | 0 |
Example
Is 176 divisible by 8?Using the rule:
176 gives 4·1+2·7+6=24
24 gives 2·2+4=8
176 is therefore divisible by 8
Is 590295810358705651712 divisible by 8?
Using the rule:
590295810358705651712 gives 4·7+2·1+2=32
32 gives 2·3+2=8
590295810358705651712 is therefore divisible by 8
divisibility by 9
Part of the table of the coefficients for the formula for 9 is below. It tells us all the coefficients are 1. This means the rule for divisibility by 9 isIf the sum of the digits is divisible by 9, then so is the number
| Power of 10 | Mod 9 |
| 1 | 1 |
| 10 | 1 |
| 100 | 1 |
| 1000 | 1 |
divisibility by 10
Part of the table of coefficients for 10 follows:| Power of 10 | Mod 10 |
| 1 | 1 |
| 10 | 0 |
| 100 | 0 |
Except for the units coefficient, all the coefficients are zero. So, if the units figure is divisible by 10, then so is the number. The only digit: 0, 1, ...9 that is divisible by 10 is 0. So:
A number is divisible by 10 if it ends in 0
Divisibility by 11
As usual, the 11's coefficients:| Power of 10 | Mod 11 | Alternative Mods |
| 1 | 1 | 1 |
| 10 | 10 | -1 |
| 100 | 1 | 1 |
| 1000 | 10 | -1 |
| 10000 | 1 | 1 |
Using the alternative mods:
A number is divisible by 11, if the sum of the differences between adjacent pairs of digits is divisible by 11
That is, abcde is divisible by 11 if:
(a-b)+(c-d)+e
is divisible by 11.
Alternatively, if we say the units digit is digit number 1 and the tens is digit number 2, etc., then:
A number is divisible by 11 if the sum of the odd placed number equals that of the even placed, or the difference is divisible by 11.
Or
A number is divisible by 11 if the difference between
Examples
55 gives 5-5=0, which is divisible by 11, so 55 is divisible132 gives 1-3+2=0, which is divisible by 11, so 132 is divisible
8679 gives 8-6 + 7-9=0, so 8679 is divisible by 11.
34716 gives (3-4)+(7-1)+6=11, which is divisible by 11, so 34716 is divisible.
Divisibility by 12
Below is the table of coefficients for 12.| Power of 10 | Mod 12 | Alternative Mods |
| 1 | 1 | 1 |
| 10 | 10 | -2 |
| 100 | 4 | 4 |
| 1000 | 4 | 4 |
The rule for 12 is:
Add the units number, ten times the tens number and 4 times the rest of the number, and if the sum is divisible by 12, so is the number.
Example
3624 gives 4+10·2+4·36=168168 gives 8+10·6+4·1=72
72 gives 2+10·7=72, which is divisible by 12
The alternative rule (using the alternative mods) is:
Subtract twice the tens digit from the units digit and add 4 times the rest of the number. If it is divisible by 12, then so is the number
Example
3624 gives 4-(2·2)+4·36=144144 gives 4-2·4+4·1=0, which is divisible by 12
Divisibility by 13
From the table below, the pattern is 1, -3, -4, -1, 3, 4, 1....| Power of 10 | Mod 13 | Alternative Mods |
| 1 | 1 | 1 |
| 10 | 10 | -3 |
| 100 | 9 | -4 |
| 1000 | 12 | -1 |
| 10000 | 3 | 3 |
| 100000 | 4 | 4 |
| 1000000 | 1 | 1 |
| 10000000 | 10 | -3 |
| 100000000 | 9 | -4 |
| 1000000000 | 12 | -1 |
| 10000000000 | 3 | 3 |
The pattern goes 1, -3, -4 and the negatives of these numbers follow: -1, 3, 4. The whole pattern repeats.
Ken Ward's Mathematics Pages
Faster Arithmetic - by Ken Ward
Ken's book is packed with examples and explanations that enable you to discover more than 150 techniques to speed up your arithmetic and increase your understanding of numbers. Paperback and Kindle:
