Divisibility Rules (2,3,5,7,11,13,17,19,...)
A divisibility rule is a heuristic for determining whether a positive integer can be evenly divided by another (i.e. there is no remainder left over). For example, determining if a number is even is as simple as checking to see if its last digit is 2, 4, 6, 8 or 0. Multiple divisibility rules applied to the same number in this way can help quickly determine its prime factorization without having to guess at its prime factors.
Contents
Basic Divisibility Rules
A positive integer is divisible by
- if the last digit of is 2, 4, 6, 8, or 0;
- if the sum of digits of is a multiple of 3;
- if the last 2 digits of are a multiple of 4;
- if the last digit of is either 0 or 5;
- if is divisible by both 2 and 3;
- if subtracting twice the last digit of from the remaining digits gives a multiple of 7 (e.g. 658 is divisible by 7 because 65 - 2 x 8 = 49, which is a multiple of 7);
- if the last 3 digits of are a multiple of 8;
- if the sum of digits of is a multiple of 9;
- if the last digit of is 0;
- if the difference of the alternating sum of digits of is a multiple of 11 (e.g. 2343 is divisible by 11 because 2 - 3 + 4 - 3 = 0, which is a multiple of 11);
- if is divisible by both 3 and 4.
Here are some example questions that can be solved using some of the divisibility rules above.
Without performing actual division, show that the number below is an integer:
From the divisibility rules, we know that a number is divisible by 12 if it is divisible by both 3 and 4. Therefore, we just need to check that 1,481,481,468 is divisible by 3 and 4.
Applying the divisibility test for 3, we get that which is divisible by 3. Hence 1,481,481,468 is divisible by 3.
Applying the divisibility test for 4, we get that the last two digits, 68, is divisible by 4. Hence 1,481,481,468 is also divisible by 4.
Now, since we know that 1,481,481,468 is divisible by both 3 and 4, it is divisible by 12. Therefore, will be an integer.
Find all the possible values of such that the number is a multiple of
From the rules of divisibility, the number is a multiple of if and only if the sum of its digits is a multiple of Since , this implies that are all the possible values.
Without performing division, explain why the number is a multiple of .
By the rule of divisibility of since is a multiple of is a multiple of
Without performing actual division, show that is not divisible by .
Applying the divisibility rule of the difference between the sum of digits at the odd places and the sum of digits at even places is which is not divisible by . Hence is not divisible by .
For what values of and is a multiple of
Since , the number must be a multiple of and
The divisibility rule of tells us that is a multiple of Since it is a number from to it must be either or
Now, the divisibility rule of tells us that is a multiple of Since it is a number from to it must be
Solving there are no integer solutions.
Solving we get .
Hence, the only solution is with and
Is divisible by
We do not know the divisibility rule of 210. However, we can easily see that , so if 65973390 is divisible by 2, 3, 5, 7, then it is divisible by 210.
- Since the last digit of 65973390 is 0, it is divisible by 2.
- Since , which is divisible by 3, it follows that 65973390 is divisible by 3.
- Since the last digit of 65973390 is 0, hence it is divisible by 5.
- To check divisibility by 7, as the initial step, we calculate . However, this number is still a little too big for us to tell whether it's divisible by 7. In such cases, we keep applying the divisibility rule again and again until we have a small enough number to work with: Now we can see that we are left with which we can easily identify as a multiple of 7. Hence 65973390 is a multiple of 7 also.
Since 65973390 is divisible by all of 2, 3, 5, 7, it is divisible by
Try some problems for yourself to see if you understand this topic:
If we know an integer is a multiple of 5, how many possibilities are there for the last two digits of the integer?
Is 87985 divisible by 7?
Intermediate Divisibility Rules
A positive integer is divisible by
- if 4 times the units digit of plus the number obtained by removing the units digit of is a multiple of 13;
- if the units digit subtracted 5 times from the remaining number (excluding the units digit) results in a number that is divisible by 17;
- if doubling the units digit and adding it to the number formed by removing the units digit in the original number is divisible by 19.
You may use these rules repeatedly until you can tell if a number is divisible by another number or not.
It is also useful to note that the notation is used to say divides , i.e. the fraction gives an integer. For example, is true, but is false.
Is divisible by
From the rules of divisibility, the number is a multiple of if and only if . Repeating the divisibility rule, we get . Repeating the rule once more, we get , which is clearly . Therefore, is not divisible by .
Is divisible by
is a composite number, so we will have to deal with it in a slightly different way. We can write as . If a number is divisible by both and , then the number is also divisible by . We choose and because they are coprime, and also because we know the divisibility rules for and .
Let's test if is divisible by . The last three digits of the number are which is divisible by , so is also divisible by . Now let's see if is divisible by . The sum of digits of is . Since is divisible by , is also divisible by . Since is divisible by both and , we can conclude that is divisible by .
Is divisible by
We do not know the divisibility rule for . However, we know that since is even, any integral multiple of will be even. However, is not even, so is not divisible by .
Is divisible by
Since , we see that it is between two consecutive multiples of . Hence is not a multiple of , and is not divisible by .
Try some problems for yourself to see if you understand this topic:
Is 986244 divisible by 13?
Divisibility Rules for Numbers
Add 7 times the last digit to the remaining truncated number. Repeat the step if necessary. If the result is divisible by 23, the original number is also divisible by 23.
- Check for 53935: which is 5 times 23. Hence 53935 is divisible by 23.
Add 3 times the last digit to the remaining truncated number. Repeat the step if necessary. If the result is divisible by 29, the original number is also divisible by 29.
- Check for 12528: which is divisible by 29. So 12528 is divisible by 29.
Subtract 3 times the last digit from the remaining truncated number. Repeat the step if necessary. If the result is divisible by 31, the original number is also divisible by 31.
- Check for 49507: Hence 49507 is divisible by 31.
Subtract 11 times the last digit from the remaining truncated number. Repeat the step if necessary. If the result is divisible by 37, the original number is also divisible by 37.
- Check for 11026: We have Since is divisible by 37, 11026 is divisible by 37.
Subtract 4 times the last digit from the remaining truncated number. Repeat the step if necessary. If the result is divisible by 41, the original number is also divisible by 41.
- Check for 14145: We have Since is divisible by 41, 14145 is divisible by 41.
Add 13 times the last digit to the remaining truncated number. Repeat the step if necessary. If the result is divisible by 43, the original number is also divisible by 43. (This process becomes difficult for most of the people because of multiplication with 13.)
- Check for 11739: We have Since 129 is divisible by 43, the 0 can be ignored. So, 11739 is divisible by 43.
Subtract 14 times the last digit from the remaining truncated number. Repeat the step if necessary. If the result is divisible by 47, the original number is also divisible by 47. (This too is difficult to operate for people who are not comfortable with table of 14.)
- Check for 45026: We have Since which is 7 times 47, 45026 is divisible by 47.
Proving Divisibility Rules
Prove that when a number is divisible by the result when subtracting twice the last digit from the number formed by the remaining digits is a multiple of
Let the number be , where is the last digit of and is the number formed by the remaining digits.
Now we have to prove that if is divisible by then must be also divisible by
Let where is an integer, and multiply this equation by and add to both sides. Then you'll get
Now move to the right, and you'll get
which is a multiple of
Prove that when a number is divisible by the last digits are a multiple of
Let the number be , where are digits and is a non-negative integer.
Clearly, is a multiple of since . Hence, is a multiple of if and only if is a multiple of
Prove that when a number is divisible by the alternating sum of digits is a multiple of
From factorization , we know that
is always a multiple of
Hence, if , then
Since the terms in the square brackets consist of multiples of it follows that is a multiple of if and only if the alternating sum is a multiple of
Finding Divisibility Rules
Although finding clever divisibility tricks requires a bit of ingenuity, finding general divisibility tests is not hard. In this section, we are only going to focus on finding divisibility tests for primes as once we know test for primes, we can decompose any composite number into primes and test for divisibility.
Let's start with an example.
Find the divisibility test for 13.
Let's first find a test for small 3-digit numbers first and then find a general test. We'll be finding tests which involves separation of last digit. These tests will be similar to the tests of 19, 23, 29, etc.
Let be any number such that . Now assume that is divisible by 13. Then
Now that we have separated the last digit from the number, we have to find a way to use it: make the coefficient of 1. In other words, we have to find an integer such that . It can be observed that the smallest which satisfies this property is 4. Now we can multiply the original equation by 4 and simplify it:
Aha! We have found out that if then . In other words, to check if a 3-digit number is divisible by 13, we can just remove the last digit, multiply it by 4, and then add it to the rest of the two digits.
Now that we have found out the test for 3-digit numbers, let's find out a general divisibility test. Let be any digit number. Then
Hence, a number is a multiple of 13 if we add 4 times the last digit to the rest of the number and the resulting number is still divisible by 13.
This process can be repeated by any arbitrary prime number to find its divisibility test. Now can you find the divisibility tests for 17, 19, 23 and 29 on your own?
Try some problems for yourself to see if you understand this topic:
One can test if an integer is divisible by prime by subtracting the last two digits (as a number) from with those digits shaved off, and see if the result is divisible by . For example, is divisible by because and .
What are the smallest factors you should multiply the last two digits of (as a number) with, before subtracting from the shaved-off in the divisibility tests for and
Give your answer as the product of the factors.