FANDOM

609 Pages

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

Every integer is divisible by one.  Example: 1289 is divisible by one, and 14461 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 consecutive numbers.

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:
1. Every integer which ends with 0, 2, 4, 6 or 8 is divisible by two.
Example:65156151594 is divisible by two because the units digit is 4, and 1597534568852 is divisible by two because the units digit is 2.
2. A number is divisible by 5 if and only if the last digit is a 0 or 5.
Example:41645 is divisible by five because the units digit is 5, and 124150 is divisible by five because the units digit is 0.
3. If the last digit of the number is 0, it is divisible by 10.
Example:158375209580 is divisible by 10 because the last digit is 0.
• Examining 2 ending digits:
1. A number is divisible by four if and only if its last two digits of the number are divisible by four.
Example:156128 is divisible by four, and 6416 is divisible by four. The last two digits are 28 and 16, respectively, both of which are divisible by 4.
2. 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:913580 is divisible by 20.
3. 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:143475 is divisible by 25.
4. 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.
5. For an integer to be divisible by 100, the last two digits need to end in 00.
• Examining 3 ending digits:
1. A number is divisible by eight if and only if its last three digits of the number are divisible by eight. [1]
Example:4313586 is divisible by 8 since the last three digits are 586, divisible by 8.
2. For an integer to be divisible by 40, the last three digits must be divisible by 40.
• Examining 4 ending digits:
1. 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.
2. For an integer to be divisible by 80, the last four digits must be divisible by 80.
• Examining 5 ending digits:
1. A number is divisible by 32 if and only if its last five digits of the number are divisible by 32.
2. For an integer to be divisible by 160, the last five digits must be divisible by 160.
• Examining 6 ending digits:
1. A number is divisible by 64 if and only if its last six digits of the number are divisible by 64.
2. 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.[2]

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.
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.
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 37.

Alternating 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.[3] 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.

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:

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:

1. Take 9 from 3409.
2. Multiply 9 by 2 (9*2=18)
3. Subtract the doubled digit to the remaining number (340-18=322)
4. Repeat the process, this time take 2 from 322.
5. Multiply 2 by 2 (2*2=4)
6. Subtract the doubled digit to the remaining number (32-4=28)
7. 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:

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:

1. Take out 9 from 85969.
2. Multiply if by four. (9 x 4 = 36)
3. Add it to the remaining digits. (8596 + 36 = 8632)
4. Take out 2 from 8632 and multiply it by four. (2 x 4 = 8)
5. Add it to the remaining digits. (863 + 8 = 871)
6. Take out 1 from 871 and multiply it by four. (1 x 4 = 4)
7. Add it to the remaining digits. (87 + 4 = 91)
8. 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:

$d$ 1-digit
R trim $x$
2-digit
R trim $x$
3 -2, 1 -2, 1
7 -2, 5 -3, 4
9 -8, 1 -8, 1
11 -1, 10 -10, 1
13 -9, 4 -10, 3
17 -5, 12 -9, 8
19 -17, 2 -15, 4
21 -2, -19 -17, 4
23 -16, 7 -20, 3
27 -8, 19 -17, 10
29 -26, 3 -20, 9
31 -3, 28 -22, 9
33 -16, 10 -32, 1
37 -11, 26 -27, 10
39 -26, 3 -23, 16
41 -4, 37 -25, 16
43 -30, 13 -3, 40
47 -33, 14 -41, 8
49 -44, 5 -24, 25
$d$ 1-digit
R trim $x$
2-digit
R trim $x$
51 -5, 46 -26, 25
53 -37, 16 -9, 44
57 -19, 40 -55, 4
59 -53, 6 -23, 36
61 -6, 55 -26, 25
63 -44, 19 -17, 46
67 -20, 47 -2, 65
69 -62, 7 -20, 49
71 -7, 64 -22, 49
73 -51, 22 -27, 46
77 -23, 54 -10, 67
79 -71, 8 -15, 64
81 -8, 73 -17, 64
83 -58, 25 -39, 44
87 -26, 61 -20, 67
89 -80, 9 -8, 81
91 -9, 82 -10, 81
93 -65, 28 -53, 40
97 -29, 68 -32, 65
99 -89, 10 -98, 1
101 -10, 91 -1, 81

Left trim

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.

$d$ Shift right
1 place
Shift right
2 places
3 1 1
6 -2 -2
7 3 2
8 2 4
9 1 1
11 -1 1
12 -2 4
13 -3 -4
14 -4 2
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: