Quick divisibility tests for small numbers in any base

The divisibility test is a fairly simple manipulation or examination of the base-n digits of the arbitrary integer x aimed at quickly determining whether x is an integer multiple of a usually small integer k. The test intends to avoid division when one merely wants to know if x is divisible by k (i.e., k | x).

We can write relatively simple divisibility tests for numbers 2 ≤ k ≤ 10 any integer base n. Certain tests may prove impractical. [1, 2]

2 | x

For even bases n, examine the rightmost digit of x. If the digit is even, then the number x is as well.

For odd bases n, add the base-n digits of x, repeat as necessary. If the sum is clearly even, x is as well.

3 | x

We use the nomenclature of threefoldness here for brevity. Here “trine” signifies that a number is divisible by 3 in much the same way that “even” means a number is divisible by 2. The opposite is “nontrine”. Nontrine numbers are either one more than a multiple of 3 (overtrine) or one less (undertrine). See this page for more.

For trine bases n = {3, 6, 9, 12, 15, …}, examine the rightmost digit of x. If the digit is trine, then the number x is as well.

For overtrine bases n = {4, 7, 10, 13, 16, …}, add the base-n digits of x, repeat as necessary. If the sum is clearly trine, x is as well.

For undertrine bases n = {2, 5, 8, 11, 14, …}, take the alternating sum of the base-n digits of x, repeat as necessary. If the sum is clearly trine, x is as well.

4 | x

We use the nomenclature of fourfoldness here for brevity. Here “quadrate” signifies that a number is divisible by 4 in much the same way that “even” means a number is divisible by 2. The opposite is “nonquadrate”. Nonquadrate numbers are either one more than a multiple of 4 (overquadrate), one less (underquadrate), or even but indivisible by 4 (counterquadrate). See this page for more.

For quadrate bases n = {4, 8, 12, 16, 20, …}, all that is required is to examine the last digit to see if it is a multiple of 4.

In counterquadrate bases n = {2, 6, 10, 14, 18, …}, we examine the rightmost pair of digits to see if it is one of n²/4 two-digit combinations. If the last pair of digits form a base-n number clearly divisible by 4, then 4 | x. If the reference range is too long, we can examine the penultimate digit to see if it is even. If so, and the last digit is quadrate, i.e., one of (0, 4, 8, digit-12, digit-16, etc.) then it is quadrate. If the penultimate digit is odd and the last digit is counterquadrate, i.e., one of (2, 6, digit-10, digit-14, etc.), then it is quadrate. [3]

For overquadrate bases n = {5, 9, 13, 17, 21, …}, 4 divides (n − 1), thus we add all the digits of the number x; if the sum is divisible by 4 so is x.

For underquadrate bases n = {3, 7, 11, 15, 19, …}, 4 divides (n + 1), take the alternating sum of the base-n digits of x, repeat as necessary. If the sum is clearly quadrate, x is as well.

5 | x

For bases that are an integer multiple of 5, examine the rightmost digit of x. If the digit is a multiple of 5, then the number x is as well.

For bases n = 5m + 1 = {6, 11, 16, 21, 26, …}, add the base-n digits of x, repeat as necessary. If the sum is clearly a multiple of 5, x is as well.

For bases n = 5m − 1 = {4, 9, 14, 19, 24, …}, take the alternating sum of the base-n digits of x, repeat as necessary. If the sum is clearly a multiple of 5, x is as well.

For bases n ≡ +2 (mod 5), {2, 7, 12, 17, 22, …}, double the rightmost base-n digit of x, then subtract from the number formed from the remaining base-n digits of x. Repeat as necessary. If the result is clearly a multiple of 5 then so is x.

For bases n ≡ −2 (mod 5), {3, 8, 13, 18, 23, …}, double the rightmost base-n digit of x, then add to the number formed from the remaining base-n digits of x. Repeat as necessary. If the sum is clearly a multiple of 5 then so is x.

Generally for any other base, i.e., bases n ≡ ±2 (mod 5), {2, 3, 7, 8, 12, 13, …}, pair the base-n digits of x starting from the right. If the alternating sum of the digit-pairs is clearly a multiple of 5, then so is x. This rule may not be as handy as either of the above two.

6 | x

For bases that are an integer multiple of 6, examine the rightmost digit of x. If the digit is a multiple of 6, then the number x is as well.

For bases n = 6m + 1 = {7, 13, 19, 25, 31, …}, add the base-n digits of x, repeat as necessary. If the sum is clearly a multiple of 6, x is as well.

For bases n = 6m − 1 = {5, 11, 17, 23, 29, …}, take the alternating sum of the base-n digits of x, repeat as necessary. If the sum is clearly a multiple of 6, x is as well.

For any other base, we may combine 2 | x and 3 | x. If both cases are true, then 6 | x. Here is a more explicit breakdown:

For otherwise trine bases (always odd) = {3, 9, 15, 21, 27, …}, 6 | x if the sum of the base-n digits of x is clearly even and if the last base-n digit of x is a multiple of 3.

For bases n = 6m+ 2, {2, 8, 14, 20, 26, …}, pair the base-n digits of x starting from the right. If the alternating sum of the digit-pairs is clearly a multiple of 3 and if the last base-n digit is even, then so is x.

For bases n = 6m − 2, {4, 10, 16, 22, 28, …}, add the base-n digits of x, repeat as necessary. If the sum is clearly a multiple of 3 and if the last base-n digit is even, then so is x.

7 | x

For bases that are an integer multiple of 7, examine the rightmost digit of x. If the digit is a multiple of 7, then the number x is as well.

For bases n = 7m + 1 = {8, 15, 22, 29, 36, …}, add the base-n digits of x, repeat as necessary. If the sum is clearly a multiple of 7, x is as well.

For bases n = 7m − 1 = {6, 13, 20, 27, 34, …}, take the alternating sum of the base-n digits of x, repeat as necessary. If the sum is clearly a multiple of 7, x is as well.

For bases n ≡ 7n + 2, {2, 9, 16, 23, 30, …}, trim the rightmost base-n digit of x, triple it, then subtract the product from the number formed from the remaining digits. Repeat as necessary. If the result is clearly a multiple of 7, then so is x.

For bases n ≡ 7n − 2, {5, 12, 19, 26, 33, …}, trim the rightmost base-n digit of x, triple it, then add the product to the number formed from the remaining digits. Repeat as necessary. If the result is clearly a multiple of 7, then so is x.

For bases n ≡ 7n + 3, {3, 10, 17, 24, 31, …}, trim the rightmost base-n digit of x, double it, then subtract the product from the number formed from the remaining digits. Repeat as necessary. If the result is clearly a multiple of 7, then so is x.

For bases n ≡ 7n − 3, {4, 11, 18, 25, 32, …}, trim the rightmost base-n digit of x, double it, then add the product to the number formed from the remaining digits. Repeat as necessary. If the result is clearly a multiple of 7, then so is x.

8 | x

For bases that are an integer multiple of 8, examine the rightmost digit of x. If the digit is a multiple of 8, then the number x is as well.

For bases n = 8m + 1 = {9, 17, 25, 33, 41, …}, add the base-n digits of x, repeat as necessary. If the sum is clearly a multiple of 8, x is as well.

For bases n = 8m − 1 = {7, 15, 23, 31, 39, …}, take the alternating sum of the base-n digits of x, repeat as necessary. If the sum is clearly a multiple of 8, x is as well.

In bases n = 8m ± 4 = {4, 12, 20, 28, 36, …}, we examine the rightmost pair of digits to see if it is one of n²/8 two-digit combinations. If the last pair of digits form a base-n number clearly divisible by 8, then 8 | x. If the reference range is too long, we can examine the penultimate digit to see if it is even. If so, and the last digit is clearly a multiple of 8, i.e., one of (0, 8, digit-16, digit-24, etc.) then 8 | x. If the penultimate digit is odd and the last digit d = 8m ± 4, i.e., one of (4, digit-12, digit-20, etc.), then 8 | x. [3]

For otherwise even bases n {2, 6, 10, 14, 18, …}, we examine the block of rightmost 3 digits to see if it is one of n³/8 two-digit combinations. If the last trio of digits form a base-n number clearly divisible by 8, then 8 | x. If the reference range is too long, we can examine the third-from-last digit to see if it is even. If so, and the last pair of digits form a base-n number clearly a multiple of 8, i.e., one of (00, 08, etc.) then 8 | x. If the penultimate digit is odd and the last two digits form a base-n number D that is 8m ± 4 then 8 | x. [3]

For any other base, i.e., bases n ≡ ±3 (mod 8), {3, 5, 11, 13, 19, 21, …}, pair the base-n digits of x starting from the right. If the sum of the base-n numbers formed from the digit-pairs is clearly a multiple of 8, then so is x.

Alternative to the immediately above, if base n ≡ 8m + 3, {3, 11, 19, 27, 35, …}, trim the rightmost base-n digit of x, triple it, then add the product to the base-n number formed from the remaining digits. Repeat as necessary. If the result is clearly a multiple of 8, then so is x.

If base n ≡ 8m + 5, {5, 13, 21, 29, 37, …}, trim the rightmost base-n digit of x, triple it, then subtract the product from the base-n number formed from the remaining digits. Repeat as necessary. If the result is clearly a multiple of 8, then so is x.

9 | x

For bases that are an integer multiple of 9, examine the rightmost digit of x. If the digit is a multiple of 9, then the number x is as well.

For bases that are trine (i.e., a multiple of 3, {3, 6, 12, 15, 21, 24, 30, …}) but not a multiple of 9, examine 2 rightmost digits of x. If the number formed by the 2 rightmost digits is a multiple of 9, then the number x is as well.

For bases n = 9m + 1 = {10, 19, 28, 37, 46, …}, add the base-n digits of x, repeat as necessary. If the sum is clearly a multiple of 9, x is as well.

For bases n = 9m − 1 = {8, 17, 26, 35, 44, …}, take the alternating sum of the base-n digits of x, repeat as necessary. If the sum is clearly a multiple of 9, x is as well.

For bases n = 9m + 2 = {11, 20, 29, 38, 47, …}, trim the rightmost base-n digit d of x and multiply it by 4, then subtract the product 4d from the number D formed from the remaining digits. Repeat as necessary. If the result D − 4d is clearly a multiple of 9, then so is x.

For bases n = 9m + 4 = {13, 22, 31, 40, 49, …}, trim the rightmost base-n digit d of x and double it, then subtract the product 2d from the number D formed from the remaining digits. Repeat as necessary. If the result D − 2d is clearly a multiple of 9, then so is x.

For bases n = 9m − 4 = {14, 23, 32, 41, 50, …}, trim the rightmost base-n digit d of x and double it, then add the product 2d to the number D formed from the remaining digits. Repeat as necessary. If the result D + 2d is clearly a multiple of 9, then so is x.

For bases n = 9m − 2 = {16, 25, 34, 43, 52, …}, trim the rightmost base-n digit d of x and multiply it by 4, then add the product 4d to the number D formed from the remaining digits. Repeat as necessary. If the result D + 4d is clearly a multiple of 9, then so is x.

10 | x

For bases that are an integer multiple of 10, examine the rightmost digit of x. If the digit is a multiple of 10, then the number x is as well.

For bases n = 10m + 1 = {11, 21, 31, 41, 51, …}, add the base-n digits of x, repeat as necessary. If the sum is clearly a multiple of 10, x is as well.

For bases n = 10m − 1 = {9, 19, 29, 39, 49, …}, take the alternating sum of the base-n digits of x, repeat as necessary. If the sum is clearly a multiple of 10, x is as well.

Generally for any other base, since 10 = 2 × 5, we may combine 2 | x and 5 | x. If both cases are true, then 10 | x. Here is a more explicit breakdown:

For bases n otherwise a multiple of 5 {5, 15, 25, 35, 45, …} (which are necessarily odd): 10 | x if the sum of the base-n digits of x is clearly even and if the last base-n digit of x is a multiple of 5.

For even bases n ≡ +1 (mod 5), {6, 16, 26, 36, 46, …}, add the base-n digits of x, repeat as necessary to get a sum S. If the rightmost digit of x is even and the sum S is clearly a multiple of 5, x is as well.

For even bases n ≡ −1 (mod 5), {4, 14, 24, 34, 44, …}, take the alternating sum of the base-n digits of x, repeat as necessary to get a sum S. If the rightmost digit of x is even and the sum S is clearly a multiple of 5, x is as well.

For even bases n ≡ +2 (mod 5), {2, 12, 22, 32, 42, …}, double the rightmost base-n digit of x, then subtract from the number formed from the remaining base-n digits of x. Repeat as necessary. If the rightmost digit of x is even and the sum S is clearly a multiple of 5, x is as well.

For even bases n ≡ −2 (mod 5), {8, 18, 28, 38, 48, …}, double the rightmost base-n digit of x, then add to the number formed from the remaining base-n digits of x. Repeat as necessary. If the rightmost digit of x is even and the sum S is clearly a multiple of 5, x is as well.

For odd bases n ≡ +2 (mod 5), {7, 17, 27, 37, 47, …}, double the rightmost base-n digit of x, then subtract from the number D formed from the remaining base-n digits of x. Repeat as necessary to obtain a result (D − 2d) clearly divisible by 5 (i.e., 5 | x) or not. Next, add the base-n digits of x, repeat as necessary. If the sum S is clearly even, x is as well (i.e., 2 | x). If both 2 | x and 5 | x are true, then 10 | x.

For odd bases n ≡ −2 (mod 5), {3, 13, 23, 33, 43, …}, double the rightmost base-n digit of x, then add it to the number D formed from the remaining base-n digits of x. Repeat as necessary to obtain a result (D + 2d) clearly divisible by 5 (i.e., 5 | x) or not. Next, add the base-n digits of x, repeat as necessary. If the sum S is clearly even, x is as well (i.e., 2 | x). If both 2 | x and 5 | x are true, then 10 | x.

12 | x

For bases that are an integer multiple of 12, examine the rightmost digit of x. If the digit is a multiple of 12, then the number x is as well.

For bases n = 12m + 1 = {13, 25, 37, 49, 61, …}, add the base-n digits of x, repeat as necessary. If the sum is clearly a multiple of 12, x is as well.

For bases n = 12m − 1 = {11, 23, 35, 47, 59, …}, take the alternating sum of the base-n digits of x, repeat as necessary. If the sum is clearly a multiple of 12, x is as well.

Generally for any other base, since 12 = 4 × 3 and 3 and 4 are coprime, we may combine 4 | x and 3 | x. If both cases are true, then 12 | x. Here is a more explicit breakdown:

For bases n otherwise divisible by 6, i.e., trine, counterquadrate n ≡ 6 (mod 12) = {6, 18, 30, 42, 54, …}, if the rightmost digit is trine (3 | x) we next check the following. We examine the rightmost pair of digits to see if it is one of n²/4 two-digit combinations. If the last pair of digits form a base-n number clearly divisible by 4, then 4 | x. If the reference range is too long, we can examine the penultimate digit to see if it is even. If so, and the last digit is quadrate, i.e., one of (0, 4, 8, digit-12, digit-16, etc.) then it is quadrate. If the penultimate digit is odd and the last digit is counterquadrate, i.e., one of (2, 6, digit-10, digit-14, etc.), then it is quadrate (4 | x). If a number is trine (3 | x) and quadrate (4 | x) it is divisible by 12.

For trine underquadrate bases n ≡ 3 (mod 12) = {3, 15, 27, 39, 51, …}, take the alternating sum of the base-n digits of x, repeat as necessary. If the sum is clearly quadrate (4 | x), and the rightmost digit d is trine (3 | x), then 12 | x.

For trine overquadrate bases n ≡ 9 (mod 12) = {9, 21, 33, 45, 57, …}, we add all the digits of the number x, repeat as necessary. If the sum is clearly quadrate (4 | x), and the rightmost digit d is trine (3 | x), then 12 | x.

For overtrine quadrate bases n ≡ 4 (mod 12) = {4, 16, 28, 40, 52, …}, add the base-n digits of x, repeat as necessary. If the sum is clearly trine (3 | x) and the rightmost digit d is a multiple of 4, then 12 | x.

For undertrine quadrate bases n ≡ 8 (mod 12) = {8, 20, 32, 44, 56, …}, take the alternating sum of the base-n digits of x, repeat as necessary. If the sum is clearly trine (3 | x) and the rightmost digit d is a multiple of 4, then 12 | x.

For overtrine counterquadrate bases n ≡ 10 (mod 12) = {10, 22, 34, 46, 58, …}, add the base-n digits of x, repeat as necessary. If the sum is clearly trine (3 | x) we next check the following. We examine the rightmost pair of digits to see if it is one of n²/4 two-digit combinations. If the last pair of digits form a base-n number clearly divisible by 4, then 4 | x. If the reference range is too long, we can examine the penultimate digit to see if it is even. If so, and the last digit is quadrate, i.e., one of (0, 4, 8, digit-12, digit-16, etc.) then it is quadrate. If the penultimate digit is odd and the last digit is counterquadrate, i.e., one of (2, 6, digit-10, digit-14, etc.), then it is quadrate (4 | x). If a number is trine (3 | x) and quadrate (4 | x) it is divisible by 12.

For undertrine counterquadrate bases n ≡ 2 (mod 12) = {2, 14, 26, 38, 50, …}, take the alternating sum of the base-n digits of x, repeat as necessary. If the sum is clearly trine (3 | x) we next check the following. We examine the rightmost pair of digits to see if it is one of n²/4 two-digit combinations. If the last pair of digits form a base-n number clearly divisible by 4, then 4 | x. If the reference range is too long, we can examine the penultimate digit to see if it is even. If so, and the last digit is quadrate, i.e., one of (0, 4, 8, digit-12, digit-16, etc.) then it is quadrate. If the penultimate digit is odd and the last digit is counterquadrate, i.e., one of (2, 6, digit-10, digit-14, etc.), then it is quadrate (4 | x). If a number is trine (3 | x) and quadrate (4 | x) it is divisible by 12.

For bases n = 12m + 5 = {5, 17, 29, 41, 53, …}, trim the rightmost base-n digit d of x and multiply it by 5, then subtract the product 5d from the number D formed from the remaining digits. Repeat as necessary. If the result D − 5d is clearly a multiple of 12, then so is x.
Alternatively, we may take sums of digits separately for 3 | x and 4 | x. Take the alternating sum A of the base-n digits of x, repeat as necessary. Take the sum S of the base-n digits of x, repeat as necessary. If A is trine (3 | x) and S is quadrate (4 | x), then 12 | x.

For bases n = 12m − 5 = {7, 19, 31, 43, 55, …}, trim the rightmost base-n digit d of x and multiply it by 5, then add the product 5d to the number D formed from the remaining digits. Repeat as necessary. If the result D + 5d is clearly a multiple of 12, then so is x.
Alternatively, we may take sums of digits separately for 3 | x and 4 | x. Take the sum S of the base-n digits of x, repeat as necessary. Take the alternating sum A of the base-n digits of x, repeat as necessary. If S is trine (3 | x) and A is quadrate (4 | x), then 12 | x.

Divisibility tests for small composite numbers with more than one distinct prime divisor

Generally, given a composite number k that has at least two distinct prime divisors p, we can produce a compound divisibility test for each of its prime power factors. For example, for k = 12 = 4 × 3, we merely need to determine 3 | x and 4 | x are both true. For For example, for k = 120 = 8 × 3 × 5, we need to determine of all three of 3 | x, 5 | x, and 8 | x are true. Given tests for the 4 smallest primes, we should have plenty of divisibility tests for most of the common numbers needed.

References

[1] McDowell, Eric L. Divisibility Tests — a History and User’s Guide. MAA Convergence. Retrieved June 2019.

[2] Marc Renault, Stupid Divisibility Tricks, (See PDF), Section 3.3, Math Horizons (2006). Retrieved in June 2019.

[3] Michael De Vlieger, Range Folding, The Number Base (29 June 2019). Retrieved in July 2019.