Divisibility Rules

For explanation of each divisibility rules sorted by order, see List of Divisibility Rules.

Divisibility rules are shorthand ways of division to tell if one number is divisible or not. They help tell whether the specific number you are looking for is prime or not. The many divisibility rules help many mathematicians and geniuses determine prime numbers, even if the number is beyond big.

Let's look at some divisibility rules:

Basic Rules

The following rules are elementary checks: Divisibility by 1 Divisibility Rule 1 Every integer is divisible by one.  Example: 2 is divisible by one. Proof: There is no need for a proof here.  Any number is divisible by one.  This rule does not apply to differentiate prime from composite numbers. Examining the last n digits Examining the last n digits Simply examine the last n digits if the divisor can divide 10n with no remainder. As such: Examining 1 ending digit: Every integer which ends with an even number (0, 2, 4, 6 or 8) is divisible by two. (Proof)Proof for Divisibility of 2: We have a base-10 number system so that when a number gets to 8 and we add two, it carries over and the last digit is 0 (because 8+2=10). Now the cycle repeats (0+2=2, 2+2=4, 4+2=6, 6+2=8) and we continue carrying over forever.  Example: 174 is divisible by two because the units digit is 4. A number is divisible by 5 if and only if the last digit is a 0 or 5. (Proof)Proof for Divisibility of 5: We first assume that every number ending in 0 or 5  is not divisible by five. Take the equation: y=5x where x is any integer constant.  Therefore, the value 5x ends with 0 or 5, since 5 multiplied by an integer constant ends with 0 or 5.   Dividing both sides by five, we get y/5 = x, an integer constant.  Therefore, even if we take the limit when x approaches infinity, we still get an integer constant.  This contradicts the assumption that every number ending in 0 or 5 is not divisible by 5. Examples: 425 is divisible by five because the units digit is 5, and 390 is divisible by five because the units digit is 0. If the last digit of the number is 0, it is divisible by 10. (Proof) Example: 600 is divisible by 10 because the last digit is 0. Examining 2 ending digits: A number is divisible by four if and only if its last two digits of the number are divisible by four. (Proof)Proof for Divisibility of 4: Since any number divisible by 4 that is divided by 4 has a remainder of 0, we can write the following, using that number as 100, let's say: $100 \equiv 0 (mod 4), 10_k \equiv 0 \pmod{4} for k=2, 3, 4 etc...$ $x \equiv a_0 + a_1 (10) + a_2 (0) + \ldots + a_k 0 \pmod{4}$ $\equiv a_0 + a_1 (10) \pmod{4}$ Therefore, x is divisible by 4 if and only if the number is divisible by 4 where a0 + a1 (10) mod 4 is the number formed by the last two digits of x. Example: 324 is divisible by four, and 484 is divisible by four. The last two digits are 24 and 84, respectively, both of which are divisible by 4. For an integer to be divisible by 20, the last two digits need to end in 20, 40, 60, 80, and 00, all of which are divisible by 20. Example: 560 is divisible by 20. For an integer to be divisible by 25, the last two digits need to end in 25, 50, 75, and 00, all of which are divisible by 25. Example: 2025 is divisible by 25. For an integer to be divisible by 50, the last two digits need to end in 50 and 00, both of which are divisible by 50. For an integer to be divisible by 100, the last two digits need to end in 00. Examining 3 ending digits: A number is divisible by eight if and only if its last three digits of the number are divisible by eight. Example: 1440 is divisible by 8 since the last three digits are 440, divisible by 8. For an integer to be divisible by 40, the last three digits must be divisible by 40. Examining 4 ending digits: A number is divisible by 16 if and only if its last four digits of the number are divisible by 16. Example: 28112 is divisible by 16 since the last four digits are 8112, divisible by 16. For an integer to be divisible by 80, the last four digits must be divisible by 80. Examining 5 ending digits: A number is divisible by 32 if and only if its last five digits of the number are divisible by 32. For an integer to be divisible by 160, the last five digits must be divisible by 160. Examining 6 ending digits: A number is divisible by 64 if and only if its last six digits of the number are divisible by 64. For an integer to be divisible by 320, the last six digits must be divisible by 320. Proof: First of all, let's suppose that 10n is divisible by d, expressed in an equation: $10^n \equiv 0 \pmod{d}$. Then, let a be an integer with k number of digits, and assume that k is larger than n: $k \ge n, k \in N$. The largest digit of a is ak, and the smallest digit is a1. $\begin{align} a & = [a_ka_{k-1} \cdots a_2a_1] \\ & = 10^n [a_ka_{k-1} \cdots a_n] + [a_{n-1} a_{n-2} \cdots a_2a_1]\\ & \equiv (a_{n-1}a_{n-2} \cdots a_2a_1) \pmod{d}\\ \end{align}$ Due to this, a is divisible by d if and only if the last n digits of a is divisible by d. Adding blocks of digits Digit sum Starting from the right to left, sum up all the digits in blocks of n digits. This works for the following numbers: 1-digit blocks 3: To put it simpler, add up all the digits and examine if the number is divisible by 3. (Proof)Proof for Divisibility of 3: This method works for divisors that are factors of 10 − 1 = 9. First of all, 9 = 10 − 1, which means 10 ≡ 1 mod 3. Now, if we are able to raise everything to the nth power, then we get 10n≡ 1n≡1 (mod 3). Since two things that are congruent modulo 3 are either both divisible by 3 or both not, we can interchange values that are congruent modulo 3. So, in a number such as the following, we can replace all the powers of 10 by 1. Afterwards, the equation gives us: $100a + 10b + 1c \equiv 1a + 1b + 1c \pmod{3}$, which is exactly the sum of the digits. Example: Examining the divisibility of 12423 by 3 — By adding all the digits together, we get 1 + 2 + 4 + 2 + 3 = 12. Since 12 is divisible by 3, the test is positive. 9: Add all the digits together. The only step different is to check if it is the multiple of 9 instead of 3. (Proof)Proof for Divisibility of 9: 9 = 10 − 1, which means 10 ≡ 1 mod 9. Any number which is one less than an integer power of ten is divisible by 9. This can be proved by expressing each number in this group as a term in the sequence Tn=T(n-1)*9+9. If T(n-1) is divisible by 9, Tn will be also. The first term in this sequence is 0 (100-1) which is divisible. Therefore, if each digit of a number is expressed as its actual place value as a sum of terms where a is the first digit, b is the second, etc. it is congruent to the sum of the digits as shown: $1000a + 100b + 10c + 1d \equiv (1000-999)a + (100-99)b$ $+ (10-9)c + (1-0)d \equiv a+b+c+d \pmod{9}$ , which is the sum of the digits. Example: Examining the divisibility of 14625 by 9 — By adding all the digits together, we get 1 + 4 + 6 + 2 + 5 = 18. Since 18 is divisible by 9, the test is positive. 2-digit blocks 11: Add up the digits in groups of two from right to left and check if the number is divisible by 11. Example: Examining the divisibility of 19074 by 11 — By adding groups of digits from right to left, we get 74 + 90 + 1 = 165. Since 165 is divisible by 11, the test is positive (if needed, one can perform the test many times). 33: Add up the digits in groups of two from right to left and check if the number is divisible by 33. 99: Add up the digits in groups of two from right to left and check if the number is divisible by 99. 3-digit blocks 27: Add up the digits in groups of three from right to left and check if the number is divisible by 27. Example: Examining the divisibility of 34803 by 27 — By adding groups of digits from right to left, we get 803 + 34 = 837. 837 is divisible by 27[A]. 37: Add up the digits in groups of three from right to left and check if the number is divisible by 37. Example: Examining the divisibility of 24215797 by 37 — By adding groups of digits from right to left, we get 797 + 215 + 24 = 1036. Applying the trick again, 36 + 1 = 37. Since 37 is divisible by 37, the test is positive[A]. 4-digit blocks 101: Add up the digits in groups of four from right to left and check if the number is divisible by 101. Alternating Sum Alt sum First, sort the numbers in groups of n digits from right to left. Alternate between adding and subtracting them. In other words, after adding the first group, continue subtracting the second group, adding the third group, subtracting the fourth group, adding the fifth group, and so on. This is called the alternating sum. This works for the following numbers: 1-digit blocks 11: From right to left, add the rightmost digit, then subtract the 2nd-to-right digit, add the 3rd-to-right digit, then subtract the 4th-to-right digit, and so on. This can be further simplified by adding all the digits in odd places and all the digits in even places separately, and then find the difference of the two. Example:For the divisibility of 527901 by 11, we first add up the digits in odd places counting from the right (in this case, 2+9+1=12), the digits in even places (in this case, 5+7+0=12). The difference is 12 - 12 = 0; therefore 527901 is divisible by 11. 2-digit blocks 101: Add up the first group of 2 digits from the right, subtract the second group, add the third group, subtract the fourth group, and so on. Example:For the divisibility of 146147 by 101, we find the alternating sum: 47 - 61 + 14 = 0. Since 0 is divisible by 101, the test is positive. 3-digit blocks 7: Find the alternating sum in groups of 3 digits from right to left. Example:For the divisibility of 1702906247 by 7, group the numbers into blocks of three (247, 906, 702, 1) and form the alternating sum (247 - 906 + 702 - 1 = 42). Since 42 = 7 * 6, 42 is divisible by 7, thus 1702906247 is divisible by 7. 13: Find the alternating sum in groups of 3 digits from right to left. Example:Take 3,692,513,279 for example, the alternating sum is -3 + 692 - 513 + 279 = 455[A]. 455 is divisible by 13, and therefore 3,692,513,279 is divisible by 13. 77: Find the alternating sum in groups of 3 digits from right to left. 77 is the product of 7 and 11. 91: Find the alternating sum in groups of 3 digits from right to left. 91 is the product of 7 and 13. 4-digit blocks 73: Find the alternating sum in groups of 4 digits from right to left. Note: A. With the 3-digit digit sum method, if the result is still not easy to determine, the "right trim method" below can be used to further examine it.

Advanced Rules

Right trim For the number a to test divisibility by d, take off the last digit, multiply it by x, and then add it to all of the remaining digits on the left. By the elementary number theory results, if the greatest common divisor of d and 10 is 1 (i.e. the number d has the last digit of 1, 3, 7, or 9), there will be a number x that can allow $10x \equiv 1 \pmod{d}$. The term for this sort of number is named inverse of 10 modulo d, and it can be written as $x \equiv 10^{(-1)} \pmod{d}$. This would allow the number to be trimmed from the right by 1 digit, multiplied by x, and then be added to the remaining digits. Similarly, there also exist a number that can allow $100x \equiv 1 \pmod{d}$, and it can be written as $x \equiv 10^{(-2)} \pmod{d}$. The number would then be able to be trimmed, multiplied by x, and then be added to the remaining digits. Examples: For the first example, to test divisibility of 3409 by 7: Testing if 3,409 is divisible by 7. Since 10x2 ≡ -1 (mod 7), we can take out the last digit, multiply it by 2, and then subtract it from the remaining digits. Therefore: Take 9 from 3409. Multiply 9 by 2 (9*2=18) Subtract the doubled digit to the remaining number (340-18=322) Repeat the process, this time take 2 from 322. Multiply 2 by 2 (2*2=4) Subtract the doubled digit to the remaining number (32-4=28) 28 is divisible by 7, so 3409 is divisible by 7. (The answer of 3409 divided by 7 is 487) Take 85969, for another example, to test divisibility of 13: Testing if 85,969 is divisible by 13. Since 10x4 ≡ 1 (mod 13), we can take out the last digit, multiply it by 4, and then add it to the remaining digits. Therefore: Take out 9 from 85969. Multiply if by four. (9 x 4 = 36) Add it to the remaining digits. (8596 + 36 = 8632) Take out 2 from 8632 and multiply it by four. (2 x 4 = 8) Add it to the remaining digits. (863 + 8 = 871) Take out 1 from 871 and multiply it by four. (1 x 4 = 4) Add it to the remaining digits. (87 + 4 = 91) 91 is divisible by 13, so 85969 is also divisible by 13. Full list below 101 Any inverse of 10 modulo d or 100 modulo d will work, thus there are two methods for the former, and two methods for the latter to do the trimming. The method can be applied to the following numbers: 1-digit or 2-digitRight trimming (3 ~ 49) $d$ 1-digit R trim $x$ 2-digit R trim $x$ Notes 3 -2, 1 -2, 1 While already covered in previous methods, an alternative method is to add 1 time the last digit to the remaining digits, or subtract 2 times the last digit to the rest. 7 -2, 5 -3, 4 To check divisibility of 7, subtract 2 times the last digit to the remaining digits. Alternatively, add 5 times the last digit to the rest. (Proof)Proof for Divisibility of 7: Every number can be expressed in the form $10x+y$, where y is the units digit. At this stage, we are trying to prove that if $x-2y$ is divisible by 7, then $10x+y$ is also divisible by 7. If $x-2y$ is divisible by 7, we can write: $x-2y=7p$, where p is a natural number. Multiply both sides by 10: $10x-20y=70p$ Add 21y to both sides:$10x+y=70p+21y$ Since $70p+21y$ is divisible by 7, we have concluded that $10x+y$ is divisible by 7 if $x-2y$ is divisible by 7. 9 -8, 1 -8, 1 While already covered in previous methods, an alternative method is to add 1 time the last digit to the remaining digits, or subtract 8 times the last digit from the rest. 11 -1, 10 -10, 1 While already covered in previous methods, an optional method is to subtract 1 time the last digit from the remaining digits, or add 1 time the last two digits to the rest. 13 -9, 4 -10, 3 To check divisibility of 13, add 4 times the last digit to the remaining digits. Alternatively, subtract 9 times the last digit to the rest. 17 -5, 12 -9, 8 To check divisibility of 17, subtract 5 times the last digit from the remaining digits. Adding 12 times the last digit is not recommended. 19 -17, 2 -15, 4 To check divisibility of 19, add 2 times the last digit to the remaining digits. 21 -2, -19 -17, 4 To check divisibility of 21, subtract 2 times the last digit from the remaining digits. 23 -16, 7 -20, 3 To check divisibility of 23, add 7 times the last digit to the remaining digits. 27 -8, 19 -17, 10 To check divisibility of 27, subtract 8 times the last digit from the remaining digits. 29 -26, 3 -20, 9 To check divisibility of 29, add 3 times the last digit to the remaining digits. 31 -3, 28 -22, 9 Subtract 3 times the last digit from the remaining digits. 33 -16, 10 -32, 1 While already covered in previous methods, it is also viable to add 10 times the last digit to the remaining digits, or add 1 time the last 2 digits to the rest. 37 -11, 26 -27, 10 While already covered in previous methods, it is also viable to subtract 11 times the last digit from the remaining digits. 39 -26, 3 -23, 16 To check divisibility of 39, add 4 times the last digit to the remaining digits. 41 -4, 37 -25, 16 Subtract 4 times the last digit from the remaining digits. 43 -30, 13 -3, 40 It is recommended to subtract 30 times the last digit from the rest instead of adding 13 times the last digit to the remaining digits. Alternatively, subtract 3 times the last 2 digits from the rest. 47 -33, 14 -41, 8 Add 8 times the last two digits to the remaining digits. 49 -44, 5 -24, 25 To check divisibility of 49, add 5 times the last digit to the remaining digits. 1-digit or 2-digit Right trimming (51 ~ 101) $d$ 1-digit R trim $x$ 2-digit R trim $x$ Notes 51 -5, 46 -26, 25 Subtract 5 times the last digit from the remaining digits. 53 -37, 16 -9, 44 Subtract 9 times the last 2 digits from the remaining digits. Alternatively, add 16 times the last digit to the rest. 57 -19, 40 -55, 4 Add 40 times the last digit to the remaining digits. Alternatively, add 4 times the last 2 digits to the rest. 59 -53, 6 -23, 36 To check divisibility of 59, add 6 times the last digit to the remaining digits. 61 -6, 55 -26, 25 Subtract 6 times the last digit from the remaining digits. 63 -44, 19 -17, 46 None of the methods are practical except perhaps adding 19 times the last digit to the rest. Check divisibility of 7 and 9 individually instead. 67 -20, 47 -2, 65 Subtract 20 times the last digit from the remaining digits. Alternatively, subtract 2 times the last 2 digits from the rest. 69 -62, 7 -20, 49 To check divisibility of 69, add 7 times the last digit to the remaining digits. 71 -7, 64 -22, 49 Subtract 6 times the last digit from the remaining digits. 73 -51, 22 -27, 46 No methods are practical for calculating mentally. Use the alternating sum method (4-digits) first before adding 22 times the last digit to the rest. 77 -23, 54 -10, 67 While already covered in previous methods, it is also viable to subtract 10 times the last 2 digits from the remaining digits. It is, however, better to check the alternating sum (3-digits) directly. 79 -71, 8 -15, 64 To check divisibility of 79, add 8 times the last digit to the remaining digits. 81 -8, 73 -17, 64 Subtract 6 times the last digit from the remaining digits. 83 -58, 25 -39, 44 Add 25 times the last digit to the remaining digits. While it is not easy to calculate, there are no simpler methods. 87 -26, 61 -20, 67 Subtract 20 times the last 2 digits from the remaining digits. While it is not easy to calculate, there are no simpler methods. 89 -80, 9 -8, 81 To check divisibility of 89, add 9 times the last digit to the remaining digits. Alternatively, subtract 80 times the last digit from the rest, or subtract 8 times the last 2 digits from the rest. 91 -9, 82 -10, 81 While already covered in previous methods, it is also viable to subtract 9 times the last digit from the remaining digits, or subtract 10 times the last 2 digits from the rest. 93 -65, 28 -53, 40 Add 40 times the last 2 digits to the remaining digits. While it is not easy to calculate, there are no simpler methods. 97 -29, 68 -32, 65 None of the methods are appreciated. See below: Left-trim. 99 -89, 10 -98, 1 While already covered in previous methods, it is also viable to add 10 times the last digit to the remaining digits, or add 1 time the last two digits to the rest. 101 -10, 91 -1, 81 While already covered in previous methods, it is also viable to subtract 10 times the last digit from the remaining digits, or subtract 1 time the last two digits from the rest. Left trim Left Trim example The trick is that, if 100 divided by the number d has a remainder of h, then the leftmost digit can be removed, multiplied by h, shifted two places to the right, and be added from there. It can be described as the following equation: $\mbox{if}~100 \equiv h\pmod{d},\ \mbox{then}~100a + b \equiv ha + b\pmod{d}.$ The same can be applied for the number 10 divided by d having a remainder h, with the same method applied to shift the leftmost digit one place to the right, and then be added from there: $\mbox{if}~10 \equiv h\pmod{d},\ \mbox{then}~10a + b \equiv ha + b\pmod{d}.$ Below is a list of numbers where this method can be applied. Only notable numbers will be listed here. Left trimming $d$ Shift right 1 place Shift right 2 places Notes 3 1 1 It is still viable to add the first digit (times 1) to the next. 6 -2 -2 7 3 2 First, take out the first digit and multiply it by 3. Then, shift that digit one place to the right, and add it from there. Alternatively, take out the first digit, double it, and then add it after moving it two places right. 8 2 4 9 1 1 It is still viable to add the first digit (times 1) to the next. 11 -1 1 It is still viable to subtract the first digit (times 1) from the next. 12 -2 4 13 -3 -4 First, take out the first digit and multiply it by 3. Then, shift that digit one place to the right, and subtract it from there. Alternatively, take out the first digit, quadruple it, shift two places to the right, and then subtract from there. 14 -4 2 First, take out the first digit and multiply it by 2. Then, shift that digit two places to the right, and add it from there. 19 ... 5 21 ... -5 32 ... 4 33 ... 1 34 ... -2 35 ... -5 48 ... 4 49 ... 2 51 ... -2 52 ... -4 53 ... -6 95 ... 5 96 ... 4 97 ... 3 98 ... 2 99 ... 1 101 ... -1

Combining Methods

This is done by testing a number's divisibility of 2 or more numbers if the divisor is a composite number that is not a square, cubic, quadratic number, etc. Suppose that d = mn where m and n are relatively prime. When the above statement is true, the number a is divisible by d if and only if d is divisible by m and d is divisible by n. For example, a number is divisible by 63 if and only if 63 is divisible by both 7 and 9. Below is a list of numbers that can apply this method: Combining methods Divisor Factors Divisor Factors Divisor Factors Divisor Factors 6 2, 3 36 4, 9 58 2, 29 82 2, 41 10 2, 5 38 2, 19 60 3, 4, 5 84 3, 4, 7 12 3, 4 39 3, 13 62 2, 31 85 5, 17 14 2, 7 40 5, 8 63 7, 9 86 2, 43 15 3, 5 42 2, 3, 7 65 5, 13 87 3, 29 18 2, 9 44 4, 11 66 2, 3, 11 88 8, 11 20 4, 5 45 5, 9 68 4, 17 90 2, 5, 9 21 3, 7 46 2, 23 69 3, 23 91 7, 13 22 2, 11 48 3, 16 70 2, 5, 7 92 4, 23 24 3, 8 50 2, 25 72 8, 9 93 3, 31 26 2, 13 51 3, 17 74 2, 37 94 2, 47 28 4, 7 52 4, 13 75 3, 25 95 5, 19 30 2, 3, 5 54 2, 27 76 4, 19 96 3, 32 33 3, 11 55 5, 11 77 7, 11 98 2, 49 34 2, 17 56 7, 8 78 2, 3, 13 99 9, 11 35 5, 7 57 3, 19 80 5, 16 100 4, 25 Combining methods D Factors D Factors 6 2, 3 58 2, 29 10 2, 5 60 3, 4, 5 12 3, 4 62 2, 31 14 2, 7 63 7, 9 15 3, 5 65 5, 13 18 2, 9 66 2, 3, 11 20 4, 5 68 4, 17 21 3, 7 69 3, 23 22 2, 11 70 2, 5, 7 24 3, 8 72 8, 9 26 2, 13 74 2, 37 28 4, 7 75 3, 25 30 2, 3, 5 76 4, 19 33 3, 11 77 7, 11 34 2, 17 78 2, 3, 13 35 5, 7 80 5, 16 36 4, 9 82 2, 41 38 2, 19 84 3, 4, 7 39 3, 13 85 5, 17 40 5, 8 86 2, 43 42 2, 3, 7 87 3, 29 44 4, 11 88 8, 11 45 5, 9 90 2, 5, 9 46 2, 23 91 7, 13 48 3, 16 92 4, 23 50 2, 25 93 3, 31 51 3, 17 94 2, 47 52 4, 13 95 5, 19 54 2, 27 96 3, 32 55 5, 11 98 2, 49 56 7, 8 99 9, 11 57 3, 19 100 4, 25

References

Important Pages
Divisibility and Sieves	Divisibility Rules (by rule) | (by list) | Sieve of Eratosthenes
Proofs and Theorems	Euclid's Proof | Goldbach's Conjecture | Prime Number Theorem | Integer
Prime Numbers	Timeline of the History of Prime Numbers | The Largest Known Prime Number
Help	Getting Started
Different Bases	What Digit a Prime Number in a Base Can End In