Divisibility rule

Step-by-step examples

Divisibility by 2

First, take any number (for this example it will be 376) and note the last digit in the number, discarding the other digits. Then take that digit (6) while ignoring the rest of the number and determine if it is divisible by 2. If it is divisible by 2, then the original number is divisible by 2.

Example

1. 376 (The original number)
2. 37 6 (Take the last digit)
3. 6 ÷ 2 = 3 (Check to see if the last digit is divisible by 2)
4. 376 ÷ 2 = 188 (If the last digit is divisible by 2, then the whole number is divisible by 2)

Divisibility by 3 or 9

First, take any number (for this example it will be 492) and add together each digit in the number (4 + 9 + 2 = 15). Then take that sum (15) and determine if it is divisible by 3. The original number is divisible by 3 (or 9) if and only if the sum of its digits is divisible by 3 (or 9).

Adding the digits of a number up, and then repeating the process with the result until only one digit remains, will give the remainder of the original number if it were divided by nine (unless that single digit is nine itself, in which case the number is divisible by nine and the remainder is zero).

This can be generalized to any standard positional system, in which the divisor in question then becomes one less than the radix; thus, in base-twelve, the digits will add up to the remainder of the original number if divided by eleven, and numbers are divisible by eleven only if the digit sum is divisible by eleven.

Example.

1. 492 (The original number)
2. 4 + 9 + 2 = 15 (Add each individual digit together)
3. 15 is divisible by 3 at which point we can stop. Alternatively we can continue using the same method if the number is still too large:
4. 1 + 5 = 6 (Add each individual digit together)
5. 6 ÷ 3 = 2 (Check to see if the number received is divisible by 3)
6. 492 ÷ 3 = 164 (If the number obtained by using the rule is divisible by 3, then the whole number is divisible by 3)

Divisibility by 4

The basic rule for divisibility by 4 is that if the number formed by the last two digits in a number is divisible by 4, the original number is divisible by 4; this is because 100 is divisible by 4 and so adding hundreds, thousands, etc. is simply adding another number that is divisible by 4. If any number ends in a two-digit number that is divisible by 4 (e.g. 24, 04, 08, etc.), then the whole number will be divisible by 4 regardless of what is before the last two digits.

Alternatively, one can just add half of the last digit to the penultimate digit (or the remaining number). If that number is an even natural number, the original number is divisible by 4.

Also, one can simply divide the number by 2, and then check the result to find if it is divisible by 2. If it is, the original number is divisible by 4. In addition, the result of this test is the same as the original number divided by 4.

Example.
General rule

1. 2092 (The original number)
2. 20 92 (Take the last two digits of the number, discarding any other digits)
3. 92 ÷ 4 = 23 (Check to see if the number is divisible by 4)
4. 2092 ÷ 4 = 523 (If the number that is obtained is divisible by 4, then the original number is divisible by 4)

Second method

1. 6174 (the original number)
2. check that last digit is even, otherwise 6174 can't be divisible by 4.
3. 61 7 4 (Separate the last 2 digits from the rest of the number)
4. 4 ÷ 2 = 2 (last digit divided by 2)
5. 7 + 2 = 9 (Add half of last digit to the penultimate digit)
6. Since 9 is not even, 6174 is not divisible by 4

Third method

1. 1720 (The original number)
2. 1720 ÷ 2 = 860 (Divide the original number by 2)
3. 860 ÷ 2 = 430 (Check to see if the result is divisible by 2)
4. 1720 ÷ 4 = 430 (If the result is divisible by 2, then the original number is divisible by 4)

Divisibility by 5

Divisibility by 5 is easily determined by checking the last digit in the number (475), and seeing if it is either 0 or 5. If the last number is either 0 or 5, the entire number is divisible by 5.

If the last digit in the number is 0, then the result will be the remaining digits multiplied by 2. For example, the number 40 ends in a zero, so take the remaining digits (4) and multiply that by two (4 × 2 = 8). The result is the same as the result of 40 divided by 5(40/5 = 8).

If the last digit in the number is 5, then the result will be the remaining digits multiplied by two, plus one. For example, the number 125 ends in a 5, so take the remaining digits (12), multiply them by two (12 × 2 = 24), then add one (24 + 1 = 25). The result is the same as the result of 125 divided by 5 (125/5=25).

Example.
If the last digit is 0

1. 110 (The original number)
2. 11 0 (Take the last digit of the number, and check if it is 0 or 5)
3. 11 0 (If it is 0, take the remaining digits, discarding the last)
4. 11 × 2 = 22 (Multiply the result by 2)
5. 110 ÷ 5 = 22 (The result is the same as the original number divided by 5)

If the last digit is 5

1. 85 (The original number)
2. 8 5 (Take the last digit of the number, and check if it is 0 or 5)
3. 8 5 (If it is 5, take the remaining digits, discarding the last)
4. 8 × 2 = 16 (Multiply the result by 2)
5. 16 + 1 = 17 (Add 1 to the result)
6. 85 ÷ 5 = 17 (The result is the same as the original number divided by 5)

Divisibility by 6

Divisibility by 6 is determined by checking the original number to see if it is both an even number (divisible by 2) and divisible by 3.

If the final digit is even the number is divisible by two, and thus may be divisible by 6. If it is divisible by 2, continue by adding the digits of the original number and checking if that sum is a multiple of 3. Any number which is both a multiple of 2 and of 3 is a multiple of 6.

Example.

1. 324 (The original number)
2. Final digit 4 is even, so 324 is divisible by 2, and may be divisible by 6.
3. 3 + 2 + 4 = 9 which is a multiple of 3. Therefore, the original number is divisible by both 2 and 3 and is divisible by 6.

Divisibility by 7

Divisibility by 7 can be tested by a recursive method. A number of the form 10x + y is divisible by 7 if and only if x − 2y is divisible by 7. In other words, subtract twice the last digit from the number formed by the remaining digits. Continue to do this until a number is obtained for which it is known whether it is divisible by 7. The original number is divisible by 7 if and only if the number obtained using this procedure is divisible by 7. For example, the number 371: 37 − (2×1) = 37 − 2 = 35; 3 − (2 × 5) = 3 − 10 = −7; thus, since −7 is divisible by 7, 371 is divisible by 7.

Similarly, a number of the form 10x + y is divisible by 7 if and only if x + 5y is divisible by 7. So add five times the last digit to the number formed by the remaining digits, and continue to do this until a number is obtained for which it is known whether it is divisible by 7.

Another method is multiplication by 3. A number of the form 10x + y has the same remainder when divided by 7 as 3x + y. One must multiply the leftmost digit of the original number by 3, add the next digit, take the remainder when divided by 7, and continue from the beginning: multiply by 3, add the next digit, etc. For example, the number 371: 3×3 + 7 = 16 remainder 2, and 2×3 + 1 = 7. This method can be used to find the remainder of division by 7.

A more complicated algorithm for testing divisibility by 7 uses the fact that 10⁰ ≡ 1, 10¹ ≡ 3, 10² ≡ 2, 10³ ≡ 6, 10⁴ ≡ 4, 10⁵ ≡ 5, 10⁶ ≡ 1, ... (mod 7). Take each digit of the number (371) in reverse order (173), multiplying them successively by the digits 1, 3, 2, 6, 4, 5, repeating with this sequence of multipliers as long as necessary (1, 3, 2, 6, 4, 5, 1, 3, 2, 6, 4, 5, ...), and adding the products (1×1 + 7×3 + 3×2 = 1 + 21 + 6 = 28). The original number is divisible by 7 if and only if the number obtained using this procedure is divisible by 7 (hence 371 is divisible by 7 since 28 is).

This method can be simplified by removing the need to multiply. All it would take with this simplification is to memorize the sequence above (132645...), and to add and subtract, but always working with one-digit numbers.

The simplification goes as follows:

• Take for instance the number 371
• Change all occurrences of 7, 8 or 9 into 0, 1 and 2, respectively. In this example, we get: 301. This second step may be skipped, except for the left most digit, but following it may facilitate calculations later on.
• Now convert the first digit (3) into the following digit in the sequence 13264513... In our example, 3 becomes 2.
• Add the result in the previous step (2) to the second digit of the number, and substitute the result for both digits, leaving all remaining digits unmodified: 2 + 0 = 2. So 301 becomes 21.
• Repeat the procedure until you have a recognizable multiple of 7, or to make sure, a number between 0 and 6. So, starting from 21 (which is a recognizable multiple of 7), take the first digit (2) and convert it into the following in the sequence above: 2 becomes 6. Then add this to the second digit: 6 + 1 = 7.
• If at any point the first digit is 8 or 9, these become 1 or 2, respectively. But if it is a 7 it should become 0, only if no other digits follow. Otherwise, it should simply be dropped. This is because that 7 would have become 0, and numbers with at least two digits before the decimal dot do not begin with 0, which is useless. According to this, our 7 becomes 0.

If through this procedure you obtain a 0 or any recognizable multiple of 7, then the original number is a multiple of 7. If you obtain any number from 1 to 6, that will indicate how much you should subtract from the original number to get a multiple of 7. In other words, you will find the remainder of dividing the number by 7. For example, take the number 186:

• First, change the 8 into a 1: 116.
• Now, change 1 into the following digit in the sequence (3), add it to the second digit, and write the result instead of both: 3 + 1 = 4. So 116 becomes now 46.
• Repeat the procedure, since the number is greater than 7. Now, 4 becomes 5, which must be added to 6. That is 11.
• Repeat the procedure one more time: 1 becomes 3, which is added to the second digit (1): 3 + 1 = 4.

Now we have a number smaller than 7, and this number (4) is the remainder of dividing 186/7. So 186 minus 4, which is 182, must be a multiple of 7.

Note: The reason why this works is that if we have: a+b=c and b is a multiple of any given number n, then a and c will necessarily produce the same remainder when divided by n. In other words, in 2 + 7 = 9, 7 is divisible by 7. So 2 and 9 must have the same remainder when divided by 7. The remainder is 2.

Therefore, if a number n is a multiple of 7 (i.e.: the remainder of n/7 is 0), then adding (or subtracting) multiples of 7 cannot change that property.

What this procedure does, as explained above for most divisibility rules, is simply subtract little by little multiples of 7 from the original number until reaching a number that is small enough for us to remember whether it is a multiple of 7. If 1 becomes a 3 in the following decimal position, that is just the same as converting 10×10ⁿ into a 3×10ⁿ. And that is actually the same as subtracting 7×10ⁿ (clearly a multiple of 7) from 10×10ⁿ.

Similarly, when you turn a 3 into a 2 in the following decimal position, you are turning 30×10ⁿ into 2×10ⁿ, which is the same as subtracting 30×10ⁿ−28×10ⁿ, and this is again subtracting a multiple of 7. The same reason applies for all the remaining conversions:

• 20×10ⁿ − 6×10ⁿ=14×10ⁿ
• 60×10ⁿ − 4×10ⁿ=56×10ⁿ
• 40×10ⁿ − 5×10ⁿ=35×10ⁿ
• 50×10ⁿ − 1×10ⁿ=49×10ⁿ

First method example
1050 → 105 − 0=105 → 10 − 10 = 0. ANSWER: 1050 is divisible by 7.

Second method example
1050 → 0501 (reverse) → 0×1 + 5×3 + 0×2 + 1×6 = 0 + 15 + 0 + 6 = 21 (multiply and add). ANSWER: 1050 is divisible by 7.

Pohlman–Mass method of divisibility by 7
The Pohlman–Mass method provides a quick solution that can determine if most integers are divisible by seven in three steps or less. This method could be useful in a mathematics competition such as MATHCOUNTS, where time is a factor to determine the solution without a calculator in the Sprint Round.

Step A: If the integer is 1000 or less, subtract twice the last digit from the number formed by the remaining digits. If the result is a multiple of seven, then so is the original number (and vice versa). For example:

112 -> 11 − (2×2) = 11 − 4 = 7 YES 98 -> 9 − (8×2) = 9 − 16 = −7 YES 634 -> 63 − (4×2) = 63 − 8 = 55 NO

Because 1001 is divisible by seven, an interesting pattern develops for repeating sets of 1, 2, or 3 digits that form 6-digit numbers (leading zeros are allowed) in that all such numbers are divisible by seven. For example:

001 001 = 1,001 / 7 = 143 010 010 = 10,010 / 7 = 1,430 011 011 = 11,011 / 7 = 1,573 100 100 = 100,100 / 7 = 14,300 101 101 = 101,101 / 7 = 14,443 110 110 = 110,110 / 7 = 15,730

01 01 01 = 10,101 / 7 = 1,443 10 10 10 = 101,010 / 7 = 14,430

111,111 / 7 = 15,873 222,222 / 7 = 31,746 999,999 / 7 = 142,857

576,576 / 7 = 82,368

For all of the above examples, subtracting the first three digits from the last three results in a multiple of seven. Notice that leading zeros are permitted to form a 6-digit pattern.

This phenomenon forms the basis for Steps B and C.

Step B: If the integer is between 1001 and one million, find a repeating pattern of 1, 2, or 3 digits that forms a 6-digit number that is close to the integer (leading zeros are allowed and can help you visualize the pattern). If the positive difference is less than 1000, apply Step A. This can be done by subtracting the first three digits from the last three digits. For example:

341,355 − 341,341 = 14 -> 1 − (4×2) = 1 − 8 = −7 YES 67,326 − 067,067 = 259 -> 25 − (9×2) = 25 − 18 = 7 YES

The fact that 999,999 is a multiple of 7 can be used for determining divisibility of integers larger than one million by reducing the integer to a 6-digit number that can be determined using Step B. This can be done easily by adding the digits left of the first six to the last six and follow with Step A.

Step C: If the integer is larger than one million, subtract the nearest multiple of 999,999 and then apply Step B. For even larger numbers, use larger sets such as 12-digits (999,999,999,999) and so on. Then, break the integer into a smaller number that can be solved using Step B. For example:

22,862,420 − (999,999 × 22) = 22,862,420 − 21,999,978 -> 862,420 + 22 = 862,442 862,442 -> 862 − 442 (Step B) = 420 -> 42 − (0×2) (Step A) = 42 YES

This allows adding and subtracting alternating sets of three digits to determine divisibility by seven. Understanding these patterns allows you to quickly calculate divisibility of seven as seen in the following examples:

Pohlman–Mass method of divisibility by 7, examples:

Is 98 divisible by seven? 98 -> 9 − (8×2) = 9 − 16 = −7 YES (Step A)

Is 634 divisible by seven? 634 -> 63 − (4×2) = 63 − 8 = 55 NO (Step A)

Is 355,341 divisible by seven? 355,341 − 341,341 = 14,000 (Step B) -> 014 − 000 (Step B) -> 14 = 1 − (4×2) (Step A) = 1 − 8 = −7 YES

Is 42,341,530 divisible by seven? 42,341,530 -> 341,530 + 42 = 341,572 (Step C) 341,572 − 341,341 = 231 (Step B) 231 -> 23 − (1×2) = 23 − 2 = 21 YES (Step A)

Using quick alternating additions and subtractions: 42,341,530 -> 530 − 341 + 42 = 189 + 42 = 231 -> 23 − (1×2) = 21 YES

Multiplication by 3 method of divisibility by 7, examples:

Is 98 divisible by seven? 98 -> 9 remainder 2 -> 2×3 + 8 = 14 YES

Is 634 divisible by seven? 634 -> 6×3 + 3 = 21 -> remainder 0 -> 0×3 + 4 = 4 NO

Is 355,341 divisible by seven? 3 × 3 + 5 = 14 -> remainder 0 -> 0×3 + 5 = 5 -> 5×3 + 3 = 18 -> remainder 4 -> 4×3 + 4 = 16 -> remainder 2 -> 2×3 + 1 = 7 YES

Find remainder of 1036125837 divided by 7 1×3 + 0 = 3 3×3 + 3 = 12 remainder 5 5×3 + 6 = 21 remainder 0 0×3 + 1 = 1 1×3 + 2 = 5 5×3 + 5 = 20 remainder 6 6×3 + 8 = 26 remainder 5 5×3 + 3 = 18 remainder 4 4×3 + 7 = 19 remainder 5 Answer is 5

Finding remainder of a number when divided by 7

7 − (1, 3, 2, −1, −3, −2, cycle repeats for the next six digits) Period: 6 digits. Recurring numbers: 1, 3, 2, −1, −3, −2
Minimum magnitude sequence
(1, 3, 2, 6, 4, 5, cycle repeats for the next six digits) Period: 6 digits. Recurring numbers: 1, 3, 2, 6, 4, 5
Positive sequence

Multiply the right most digit by the left most digit in the sequence and multiply the second right most digit by the second left most digit in the sequence and so on and so for. Next, compute the sum of all the values and take the modulus of 7. Example: What is the remainder when 1036125837 is divided by 7?

Multiplication of the rightmost digit = 1 × 7 = 7

Multiplication of the second rightmost digit = 3 × 3 = 9

Third rightmost digit = 8 × 2 = 16

Fourth rightmost digit = 5 × −1 = −5

Fifth rightmost digit = 2 × −3 = −6

Sixth rightmost digit = 1 × −2 = −2

Seventh rightmost digit = 6 × 1 = 6

Eighth rightmost digit = 3 × 3 = 9

Ninth rightmost digit = 0

Tenth rightmost digit = 1 × −1 = −1

Sum = 33

33 modulus 7 = 5

Remainder = 5

Digit pair method of divisibility by 7

This method uses 1, −3, 2 pattern on the digit pairs. That is, the divisibility of any number by seven can be tested by first separating the number into digit pairs, and then applying the algorithm on three digit pairs (six digits). When the number is smaller than six digits, then fill zero's to the right side until there are six digits. When the number is larger than six digits, then repeat the cycle on the next six digit group and then add the results. Repeat the algorithm until the result is a small number. The original number is divisible by seven if and only if the number obtained using this algorithm is divisible by seven. This method is especially suitable for large numbers.

Example 1:
The number to be tested is 157514. First we separate the number into three digit pairs: 15, 75 and 14.
Then we apply the algorithm: 1 × 15 − 3 × 75 + 2 × 14 = 182
Because the resulting 182 is less than six digits, we add zero's to the right side until it is six digits.
Then we apply our algorithm again: 1 × 18 − 3 × 20 + 2 × 0 = −42
The result −42 is divisible by seven, thus the original number 157514 is divisible by seven.

Example 2:
The number to be tested is 15751537186.
(1 × 15 − 3 × 75 + 2 × 15) + (1 × 37 − 3 × 18 + 2 × 60) = −180 + 103 = −77
The result −77 is divisible by seven, thus the original number 15751537186 is divisible by seven.

Another digit pair method of divisibility by 7

Method

This is a non-recursive method to find the remainder left by a number on dividing by 7:

1. Separate the number into digit pairs starting from the ones place. Prepend the number with 0 to complete the final pair if required.
2. Calculate the remainders left by each digit pair on dividing by 7.
3. Multiply the remainders with the appropriate multiplier from the sequence 1, 2, 4, 1, 2, 4, ... : the remainder from the digit pair consisting of ones place and tens place should be multiplied by 1, hundreds and thousands by 2, ten thousands and hundred thousands by 4, million and ten million again by 1 and so on.
4. Calculate the remainders left by each product on dividing by 7.
5. Add these remainders.
6. The remainder of the sum when divided by 7 is the remainder of the given number when divided by 7.

For example:

The number 194,536 leaves a remainder of 6 on dividing by 7.

The number 510,517,813 leaves a remainder of 1 on dividing by 7.

Proof of correctness of the method

The method is based on the observation that 100 leaves a remainder of 2 when divided by 7. And since we are breaking the number into digit pairs we essentially have powers of 100.

1 mod 7 = 1

100 mod 7 = 2

10,000 mod 7 = 2^2 = 4

1,000,000 mod 7 = 2^3 = 8; 8 mod 7 = 1

100,000,000 mod 7 = 2^4 = 16; 16 mod 7 = 2

10,000,000,000 mod 7 = 2^5 = 32; 32 mod 7 = 4

And so on.

The correctness of the method is then established by the following chain of equalities:

Let N be the given number ${\displaystyle \overline{a_{2n}{a}_{2n-1}...a_2{a}_1}}$.

${\displaystyle \overline{a_{2n}{a}_{2n-1}...a_2{a}_1}\mathrm{mod}7}$

${\displaystyle [\sum _{k=1}^n(a_{2k}{a}_{2k-1})\times {10}^{2k-2}]mod7}$

${\displaystyle \sum _{k=1}^n(a_{2k}{a}_{2k-1}\times {10}^{2k-2})mod7}$

${\displaystyle \sum _{k=1}^n(a_{2k}{a}_{2k-1}mod7)\times ({10}^{2k-2}mod7)}$

Another digit grouping method of divisibility by 7

Method

This method determines whether an integer is divisible by 7 by grouping digits in sets of three:

Starting from the right (units place), divide the number into groups of three digits. If necessary, prepend leading zeros to complete the leftmost group.

Starting from the rightmost group, alternately add and subtract the groups moving left. That is, subtract the second group from the first, add the third, subtract the fourth, and so on. Evaluate the resulting sum. If the result is divisible by 7, then the original number is divisible by 7; otherwise, it is not.

Example

To test the number 10,517,815:

Group the digits:

010 | 517 | 815

Apply alternating operations:

815 − 517 + 010 = 308

Since 308 is divisible by 7, the original number is also divisible by 7.

Proof of correctness

This method is based on modular arithmetic. Observe that:

1000 ≡ −1 (mod 7)

since 1000 leaves a remainder of 6 when divided by 7, and 6 ≡ −1 (mod 7).

Any integer can be expressed as a sum of multiples of powers of 1000:

N = a₀ + a₁·1000 + a₂·1000² + a₃·1000³ + ...

Reducing modulo 7:

N ≡ a₀ − a₁ + a₂ − a₃ + ... (mod 7)

Thus, the alternating sum of the three-digit groups is congruent to the original number modulo 7. Therefore, the original number is divisible by 7 if and only if this alternating sum is divisible by 7.

Divisibility by 11

Method

In order to check divisibility by 11, consider the alternating sum of the digits. For example with 907,071:

${\displaystyle 9-0+7-0+7-1=22=2\times 11,}$

so 907,071 is divisible by 11.

We can either start with ${\displaystyle -}$ or ${\displaystyle +}$ since multiplying the whole by ${\displaystyle -1}$ does not change anything.

Proof of correctness of the method

Considering that ${\displaystyle 10\equiv -1mod11}$, we can write for any integer:

${\displaystyle \overline{a_n{a}_{n-1}...a_1{a}_0}=\sum _{i=0}^n{a}_i{10}^i\equiv \sum _{i=0}^n(-1{)}^i{a}_{i}mod11.}$

Divisibility by 13

Remainder Test 13 (1, −3, −4, −1, 3, 4, cycle goes on.) If you are not comfortable with negative numbers, then use this sequence. (1, 10, 9, 12, 3, 4)

Multiply the right most digit of the number with the left most number in the sequence shown above and the second right most digit to the second left most digit of the number in the sequence. The cycle goes on.

Example: What is the remainder when 321 is divided by 13?
Using the first sequence,
Ans: 1 × 1 + 2 × −3 + 3 × −4 = −17
Remainder = −17 mod 13 = 9

Example: What is the remainder when 1234567 is divided by 13?
Using the second sequence,
Answer: 7 × 1 + 6 × 10 + 5 × 9 + 4 × 12 + 3 × 3 + 2 × 4 + 1 × 1 = 178 mod 13 = 9
Remainder = 9

A recursive method can be derived using the fact that ${\displaystyle 10=-3mod13}$ and that ${\displaystyle {10}^{-1}=4mod13}$. This implies that a number is divisible by 13 iff removing the first digit and subtracting 3 times that digit from the new first digit yields a number divisible by 13. We also have the rule that 10 x + y is divisible iff x + 4 y is divisible by 13. For example, to test the divisibility of 1761 by 13 we can reduce this to the divisibility of 461 by the first rule. Using the second rule, this reduces to the divisibility of 50, and doing that again yields 5. So, 1761 is not divisible by 13.

Testing 871 this way reduces it to the divisibility of 91 using the second rule, and then 13 using that rule again, so we see that 871 is divisible by 13.

Beyond 30

Divisibility properties of numbers can be determined in two ways, depending on the type of the divisor.

Alternatively the tests for divisibility can be grouped into tests examining the ending digits, taking the sum of the digits, taking an alternating sum of digits, trimming from the right, trimming from the left and factoring the divisor.

Composite divisors

A number is divisible by a given divisor if it is divisible by the highest power of each of its prime factors. For example, to determine divisibility by 36, check divisibility by 4 and by 9. Note that checking 3 and 12, or 2 and 18, would not be sufficient. A table of prime factors may be useful.

A composite divisor may also have a rule formed using the same procedure as for a prime divisor, given below, with the caveat that the manipulations involved may not introduce any factor which is present in the divisor. For instance, one cannot make a rule for 14 that involves multiplying the equation by 7. This is not an issue for prime divisors because they have no smaller factors.

To test the divisibility of a number by a power of 2 or a power of 5 (2ⁿ or 5ⁿ, in which n is a positive integer), one only need to look at the last n digits of that number.

To test divisibility by any number expressed as the product of prime factors ${\displaystyle p_1^n{p}_2^m{p}_3^q}$, we can separately test for divisibility by each prime to its appropriate power. For example, testing divisibility by 24 (24 = 8 × 3 = 2³ × 3) is equivalent to testing divisibility by 8 (2³) and 3 simultaneously, thus we need only show divisibility by 8 and by 3 to prove divisibility by 24.

Prime divisors

The goal is to find an inverse to 10 modulo the prime under consideration (does not work for 2 or 5) and use that as a multiplier to make the divisibility of the original number by that prime depend on the divisibility of the new (usually smaller) number by the same prime. Using 31 as an example, since 10 × (−3) = −30 = 1 mod 31, we get the rule for using y − 3x in the table below. Likewise, since 10 × (28) = 280 = 1 mod 31 also, we obtain a complementary rule y + 28x of the same kind - our choice of addition or subtraction being dictated by arithmetic convenience of the smaller value. In fact, this rule for prime divisors besides 2 and 5 is really a rule for divisibility by any integer relatively prime to 10. This is why the last divisibility condition for any number relatively prime to 10 has the same kind of form (add or subtract some multiple of the last digit from the rest of the number).

Generalized divisibility rule

Divisors Ending in 1, 3, 7, or 9 in base 10

To test for divisibility by D, where D ends in 1, 3, 7, or 9, the following method can be used. Find any multiple of D ending in 9. (If D ends respectively in 1, 3, 7, or 9, then multiply by 9, 3, 7, or 1.) Then add 1 and divide by 10, denoting the result as m. Then a number N = 10t + q is divisible by D if and only if mq + t is divisible by D. If the number is too large, you can also break it down into several strings with e digits each, satisfying either 10^e = 1 or 10^e = −1 (mod D). The sum (or alternating sum) of the numbers have the same divisibility as the original one.

For example, to determine whether 913 = 10 × 91 + 3 is divisible by 11, find that m = (11 × 9 + 1) ÷ 10 = 10. Then mq + t = 10 × 3 + 91 = 121; this is divisible by 11 (with quotient 11), so 913 is also divisible by 11. As another example, to determine whether 689 = 10 × 68 + 9 is divisible by 53, find that m = (53 × 3 + 1) ÷ 10 = 16. Then mq + t = 16 × 9 + 68 = 212, which is divisible by 53 (with quotient 4); so 689 is also divisible by 53.

Alternatively, any number Q = 10c + d is divisible by n = 10a + b, such that gcd(n, 2, 5) = 1, if c + D(n)d = An for some integer A, where $${\displaystyle D(n)\equiv \{\begin{array}{ll}9a+1& \text{if }n=10a+1,\\ 3a+1& \text{if }n=10a+3,\\ 7a+5& \text{if }n=10a+7,\\ a+1& \text{if }n=10a+9.\end{array}}$$

The first few terms of the sequence, generated by D(n), are 1, 1, 5, 1, 10, 4, 12, 2, ... (sequence A333448 in the OEIS).

The piece wise form of D(n) and the sequence generated by it were first published by Bulgarian mathematician Ivan Stoykov in March 2020.

Divisors that are powers of a factor of the base

For D in base b, where there exists some ${\displaystyle n\in \mathbb{N}}$, and ${\displaystyle d|b}$ such that ${\displaystyle D={\left(\frac{b}{d}\right)}^n}$, the following is a test to check if some number u is divisible by D. Take u' equal to u truncated to the lowest n digits in base b. The divisibility of u by D is the same as the divisibility of u' by D. Multiply u' by ${\displaystyle d^n}$, if the number of trailing zeros in the product is greater than or equal to n, then u is divisible by D. Truncating u is not strictly necessary but is generally faster.

Proofs

Proof using basic algebra

Many of the simpler rules can be produced using only algebraic manipulation, creating binomials and rearranging them. By writing a number as the sum of each digit times a power of 10 each digit's power can be manipulated individually.

Case where all digits are summed

This method works for divisors that are factors of 10 − 1 = 9.

Using 3 as an example, 3 divides 9 = 10 − 1. That means ${\displaystyle 10\equiv 1(\mathrm{mod}3)}$ (see modular arithmetic). The same for all the higher powers of 10: ${\displaystyle {10}^n\equiv 1^n\equiv 1(\mathrm{mod}3).}$ They are all congruent to 1 modulo 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:

${\displaystyle 100\cdot a+10\cdot b+1\cdot c\equiv (1)a+(1)b+(1)c(\mathrm{mod}3),}$

which is exactly the sum of the digits.

Case where the alternating sum of digits is used

This method works for divisors that are factors of 10 + 1 = 11.

Using 11 as an example, 11 divides 11 = 10 + 1. That means ${\displaystyle 10\equiv -1(\mathrm{mod}11)}$. For the higher powers of 10, they are congruent to 1 for even powers and congruent to −1 for odd powers:

${\displaystyle {10}^n\equiv (-1{)}^n\equiv \{\begin{array}{ll}1& \text{if }n\text{ is even},\\ -1& \text{if }n\text{ is odd}\end{array}(\mathrm{mod}11).}$

Like the previous case, we can substitute powers of 10 with congruent values:

${\displaystyle 1000\cdot a+100\cdot b+10\cdot c+1\cdot d\equiv (-1)a+(1)b+(-1)c+(1)d(\mathrm{mod}11),}$

which is also the difference between the sum of digits at odd positions and the sum of digits at even positions.

Case where only the last digit(s) matter

This applies to divisors that are a factor of a power of 10. This is because sufficiently high powers of the base are multiples of the divisor, and can be eliminated.

For example, in base 10, the factors of 10¹ include 2, 5, and 10. Therefore, divisibility by 2, 5, and 10 only depend on whether the last 1 digit is divisible by those divisors. The factors of 10² include 4 and 25, and divisibility by those only depend on the last 2 digits.

Case where only the last digit(s) are removed

Most numbers do not divide 9 or 10 evenly, but do divide a higher power of 10ⁿ or 10ⁿ − 1. In this case the number is still written in powers of 10, but not fully expanded.

For example, 7 does not divide 9 or 10, but does divide 98, which is close to 100. Thus, proceed from

${\displaystyle 100\cdot a+b,}$

where in this case a is any integer, and b can range from 0 to 99. Next,

${\displaystyle (98+2)\cdot a+b,}$

and again expanding

${\displaystyle 98\cdot a+2\cdot a+b,}$

and after eliminating the known multiple of 7, the result is

${\displaystyle 2\cdot a+b,}$

which is the rule "double the number formed by all but the last two digits, then add the last two digits".

Case where the last digit(s) is multiplied by a factor

The representation of the number may also be multiplied by any number relatively prime to the divisor without changing its divisibility. After observing that 7 divides 21, we can perform the following:

${\displaystyle 10\cdot a+b,}$

after multiplying by 2, this becomes

${\displaystyle 20\cdot a+2\cdot b,}$

and then

${\displaystyle (21-1)\cdot a+2\cdot b.}$

Eliminating the 21 gives

${\displaystyle -1\cdot a+2\cdot b,}$

and multiplying by −1 gives

${\displaystyle a-2\cdot b.}$

Either of the last two rules may be used, depending on which is easier to perform. They correspond to the rule "subtract twice the last digit from the rest".

Proof using modular arithmetic

This section will illustrate the basic method; all the rules can be derived following the same procedure. The following requires a basic grounding in modular arithmetic; for divisibility other than by 2's and 5's the proofs rest on the basic fact that 10 mod m is invertible if 10 and m are relatively prime.

For 2n or 5n

Only the last n digits need to be checked.

${\displaystyle {10}^n=2^n\cdot 5^n\equiv 0(\mathrm{mod}{2}^n\text{ or }{5}^n).}$

Representing x as ${\displaystyle {10}^n\cdot y+z,}$

${\displaystyle x={10}^n\cdot y+z\equiv z(\mathrm{mod}{2}^n\text{ or }{5}^n),}$

and the divisibility of x is the same as that of z.

For 7

Since 10 × 5 ≡ 10 × (−2) ≡ 1 (mod 7), we can do the following:

Representing x as ${\displaystyle 10\cdot y+z,}$

${\displaystyle -2x\equiv y-2z(\mathrm{mod}7),}$

so x is divisible by 7 if and only if y − 2z is divisible by 7.