Divisibility Test Glossary

Home Glossary

Divisibility Test

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

In this essay we will denote a divisibility test with the notation k | x. The evenness or parity test thus is represented as 2 | x, while a test for divisibility by 5 is represented as 5 | x.

Links to sections:

1. A practical shortcut.
2. Simple and common divisibility tests.
3. Types of divisibility tests.
   n^m | x: examine trailing zeros.
   r | x: the regular test.
   ω | x: the omega or digit-sum test.
   α | x: the alpha or alternating sum test.
   ω₂ | x: the omega-2 test.
   α₂ | x: the alpha-2 test.
   The right trim test.
   The left trim test.
   Compound tests.
4. Opaque numbers k in base n.
5. Popularity of divisibility tests.

(Back to top ↑)

A practical shortcut

(Back to top ↑)

Divisibility tests are intended to be practical, meaning that it should be faster and more convenient than dividing x/k, given an already-memorized divisibility rule. We also presume that the number x has a reasonable number of digits, say, around a dozen or less, or perhaps small enough not to have to resort to scientific notation. It can be demonstrated, as it is in [1] that a divisibility test k | x can be written for any number k > 1 in base n > 1. In this work we consider the most practical “intuitive” divisibility tests which largely concern prime-power factors of n or left- or right-trim tests if the first are not available.

Examples of commonly-known divisibility tests appear at sources aimed at elementary school children such as [2, 3]. Indeed other sites offer a more comprehensive list, though in this work we are interested in the most widely known, easily learned, and practical tests so as to project which perhaps might be popular were we to have developed as a base n society rather than a decimal one. It must be emphasized that such tests are taught to children in the lower grades to be mastered for use in more advanced arithmetic, principally, fraction simplification and arithmetic involving fractions and ratios.

See [5] for simple divisibility tests to see if an arbitrary number x is a multiple of 2 ≤ k ≤ 8 in any base n.

Simple and common divisibility tests

(Back to top ↑)

For the purposes of this work, we assign the term “intuitive” to certain divisibility tests that pertain to trailing zeros or prime-power factors of n. We shall list them below. First, let’s recall the prime power decomposition (commonly called the factorization) of k.

Let k = p₁^e1 × p₂^e2 × … × p_i^ei,
where p₁ < p₂ < … < p_i,

A prime power factor of k is simply one of the prime powers p^e that produce n. For instance we can express k = 12 = 2² × 3, where 2² = 4 and 3 are prime power factors. The maximum number of sources for divisibility tests is the same as the number of distinct prime divisors of k, i.e., “little omega” ω(k). Therefore, for k = 12, we can have 12 | x, or 12 can inherit tests from 3 | x and 4 | x, depending on the arithmetic relationship of base n and 12.

The intuitive divisibility tests, for the purpose of this work, include the regular test (for r | n^ε), and the neighbor-factor tests, specifically the alpha test (for t_α | (n + 1)) and omega test (for t_ω | (n − 1)).

The assertion of the simplicity of the regular and neighbor-factor tests is corrobborated by [6: p. 228].

Opacity of certain k in base n

When an intuitive divisibility test is unavailable for at least one prime power factor of k, we say k is “opaque” in this work. A society that uses base n would likely turn to other methods to produce a divisibility test for certain small opaque k. For instance, in base n = 12, k = 5 is neither regular nor a neighbor-factor; it is opaque. However, 5 is a reasonably small prime, its importance between that of 3 (regular) and 7 (also opaque). Therefore a duodecimal civilization might turn to the alpha-2 test for 5 | x and its many multiples (10, 15, 20, 30, 40, 45, 55, 60, …) which involve regular or neighbor factors. Similarly, in base ten we see the right trim (−2) test for 7 | x put forth in sources like [2]. In base twelve where 7 is also opaque, we would use right trim (+3) for for 7 | x. Perhaps such a test would be regarded as useful in a duodecimal world as it is decimally.

At a certain point, especially given the easy access to modern computation in calculators and smartphones, we might see certain divisibility tests drop out of societal consciousness. The simplest tests, including the practical intuitive tests, would tend to remain in memory as the Rule of 3 remains today in our decimal world.

Types of Divisibility Tests.

 

n^m | x: examine trailing zeros

(Back to top ↑)

The simplest divisibility test in base n is perhaps n | x. In such a test, we examine the last digit of x to see if it is 0. If it is, then n | x.

Similarly, we can determine if n^m | x if x has m trailing zeros. For example, decimally, we know 825,000 is divisible by 1000, since it has 3 zeros at the end. This test is practical so long as we can reliably count zeros. This rule operates in any base n > 1. [1, 4, 6]

r | x: the regular test

(Back to top ↑)

Let the n-regular number r | n^ε with richness ε ≥ 0. The divisor d | n is a special case; the richness of a divisor d > 1 is 1. These tests involve examination of a block of the least significant, rightmost digits of x to see if it is a multiple of k. We compare the block to a list of combinations that each have ε digits. In this work we call the list a reference range. The number of combinations we will term its breadth for the sake of this essay. There are n^ε/r combinations in the reference range for r | x. We note that n^m | x above is a type of regular test. [1, 4, 6]

d | x: the divisor test

For any divisor d | n, we examine the last digit of x to see if it is in the reference range. Each of the n/d combinations in the reference range have a single digit. Example: in decimal, we know x is a multiple of d = 2 if the last digit of x is one of {0, 2, 4, 6, 8} (5 combinations). Conversely, we know that x is a multiple of d = 5 if the last digit of x is either 0 or 5. In base 14, x (expressed in base 14) is a multiple of d = 7 if the last tetradecimal digit of x is either 0 or 7. We observe that these tests tend to be more practical for d > √n, since there are fewer combinations in the reference range. For decimal 5 | x, we have a breadth of 2, but for 2 | x, the number of combinations in the reference range is 5.

Impracticality on account of breadth

Regarding the evenness test 2 | x in even bases n, at some point the number n/2 of even combinations in the reference range exceeds the human ability to memorize. Recall that small children would be required to learn the even numbers early. Therefore the evenness test is the first regular test to prove impractical on account of breadth as even n increases. Given the lesser round of about 30, the evenness test begins to become impractical around n = 60, the regular test 3 | x around n = 90, etc.

r | x: nondivisor regular test

Regular tests r | x can be written for nondivisors (semidivisors). These involve observing a block of more than one final digit.

Decimal examples:

4 | x: A number x is a multiple of r = 4 | 10² if the last digit of x is one of 10²/4 = 25 two-digit combinations {00, 04, 08, 12, 16, …, 96}.

8 | x: A number x is a multiple of r = 8 | 10³ if the last digit of x is one of 10³/8 = 125 three digit combinations {000, 008, 016, …, 992}. This test may prove impractical to many. We can apply range folding to this test and render it practical: A number x is a multiple of r = 8 | 10³ if the 3rd-to last digit is even and the last 2 digits of x are one of {00, 08, 16, 24, 32, …, 88, 96} (13 combinations) or the 3rd-to-last digit is odd and the last 2 digits are one of {04, 12, 20, 28, …, 84, 92} (12 combinations).

Duodecimal (base 12) examples:

8 | x: A number x is a multiple of r = 8 | 12² if the last digit of x is one of 12²/8 = 18 two-digit combinations {00, 08, 14, 20, 28, …, b4}.

9 | x: A number x is a multiple of r = 9 | 12² if the last digit of x is one of 12²/9 = 16 two-digit combinations {00, 09, 16, 23, …, b3}.

Range folding

Main article: range folding.

We can reduce the breadth of certain regular numbers r by applying a simple prime divisor test P | x on a digit that is not final. The number r must be composite, and the prime P is practically limited to 2 or 3. The prime P = 3 requires the nomenclature of threefoldness to go smoothly, which would foreseeably be in play in a base n that is a multiple of 3. Notably, range folding is useful for decimal 8 | x and perhaps duodecimal 9 | x; it is not a commonly practical technique. See this link for more about range folding.

ω | x: the omega or digit-sum test

Main article: omega number. (Back to top ↑)

Let the omega number ω = (n − 1), and let the omega factor t_ω | (n − 1), in other words, a divisor of (n − 1). These numbers are coprime to n. We may use the digit sum to determine whether (n − 1) | x in base n. [1, 4, 6]

Generally, x is a multiple of (n − 1) if the total of all the base-n digits of x are clearly a multiple of (n − 1).

This rule also applies to any omega factor t_ω. The number x is a multiple of t_ω if the total of all the base-n digits of x are clearly a multiple of t_ω.

The Rule of 3 and 9 in base 10 are omega tests. In decimal, we know x is a multiple of 3 if the total of all the digits of x are clearly a multiple of 3. We know x is a multiple of 9 if the total of all the digits of x are clearly a multiple of 9. In base 15, the omega test pertains to 2 and 7.

The rule is simple and practical so long as the base-n integer length of x is not unwieldy. It ranks among the most practical divisibility tests in any base. The omega rule is often more practical than regular tests when the breadth of the reference range is too large. For even bases larger than 60, the omega test is more practical than the evenness test.

The omega test is most useful when (n − 1) is composite and furnishes tests for small nondivisor primes q. In base 10 = 2 × 5, the omega test furnishes a test for q = 3 and its square, 9. This renders the factor 3 of x rather transparently despite the fact 3 does not divide 10. Perhaps we would see the omega test as “wasted” on a large q = 11 in base 12, since 11 | x is rarely necessary.

Examples:

3 | x: In decimal we know 728 is not divisible by 3 since its digit sum is 17, which is not a multiple of 3. (The number 728 = 3⁶ − 1).

5 | x: In hexadecimal (base 16) we know “271” is a multiple of 5 since its digit sum is “a” (digit ten), clearly a multiple of 5. (Hexadecimal “271” = decimal 625 = 5⁴).

3 | x: In hexadecimal (base 16) we know “c5c1” is a multiple of 3 since its digit sum is “1e”, but if that is not clear, then we repeat the digit sum and result in “f” (digit fifteen), clearly a multiple of 3. Additionally, since the sum is also divisible by 5, we know that “c5c1” is also a multiple of 5 and fifteen. (Hexadecimal “c5c1” = decimal 50625 = 15⁴).

Evenness in odd bases

For odd bases n, the number k = 2 divides both (n − 1) and (n + 1), because both are even. The omega test is simpler than the alpha, thus we use the digit sum to determine whether x is even or odd in an odd base n.

In odd base n, a number x is even if the sum of the base-n digits of x is clearly even.

Note: we cannot tell that a number is even in an odd base merely by looking at its last digit to see that it is even! This is because 2 is nonregular in an odd base.

Examples:

2 | x: In quinary (base 5), we know the number “2011” is even since the sum of digits is “4”, which is clearly even. Therefore quinary “2011” is even. (“2011” = 64 decimal).

2 | x: In pentadecimal (base 15), we know the number “9a98” is even since the sum of digits is “26”. It might still be unclear that “26” is even, thus we repeat the sum to result in the total “8”, which is clearly even. Therefore pentadecimal “9a98” is even. (“9a98” = 2¹⁵).

α | x: the alpha or alternating sum test

Main article: alpha number. (Back to top ↑)

Let the alpha number α = (n + 1), and let the alpha factor t_α | (n + 1), in other words, a divisor of (n + 1). These numbers are coprime to n. In any base, the alpha number is always written “11” assuming standard positional notation and Hindu-Arabic numerals. We may use the alternating sum to determine whether (n + 1) | x in base n. The alternating sum is the result of adding every other digit, then adding the digits that were not summed in the first total, and subtracting the second from the first sum. For instance, given the number 12345, the alternating sum is (1 + 3 + 5) − (2 + 4) = 8 − 6 = 2. [1, 4, 6]

Generally, x is a multiple of (n + 1) if the alternating sum of all the base-n digits of x are clearly a multiple of (n + 1).

This rule also applies to any alpha factor t_α. The number x is a multiple of t_α if the alternating sum of all the base-n digits of x are clearly a multiple of t_α.

Examples:

11 | x: In base 10, the alpha number is (10 + 1) = 11. Therefore, the number x is a multiple of 11 if the alternating sum of its decimal digits is clearly a multiple of 11. The number 14640 is not a multiple of 11 because (1 + 6 + 0) − (4 + 4) = 7 − 8 = −1 is not an integer multiple of 11. (Note that 14640 = 11⁴ − 1).

3 | x: In tetradecimal (base 14), the alpha rule is more useful since tetradecimal “11” = 3 × 5. Therefore we know the number “47” is a multiple of 3 since the tetradecimal alternating digit sum (4 − 7) = −3 is clearly a multiple of 3. We also know that “47” is a multiple of 7 since the number 7 is a divisor of the base, and since the number ends in one of {0, 7}. (Tetradecimal “47” = 3² × 7 = decimal 63). We know it is not divisible by 5, since that alternating sum is clearly not a multiple of 5. In base 14, the omega rule pertains to 13 and is not quite as useful, therefore tetradecimal divisibility tests are dominated by alpha, whereas decimal tests are omega-dominant.

ω₂ | x: the omega-2 test

Main article: omega-2. (Back to top ↑)

Consider ω₂ = (n² − 1), a number that may be factored algebraically as (n + 1)(n − 1). We recognize these factors as the alpha and omega numbers described above. We consider factors t_ω2 | ω₂ outside of (n + 1) and (n − 1) omega-2 factors. These numbers are coprime to n. We may use the digit sum applied to blocks of paired digits starting from the radix point and working leftward to determine whether t_ω2 | x in base n. An example of the digit sum applied to paired digits: for a number “12345”, we add “1” + “23” + “45”, which in bases n > 9 is written “69”. In that number “12345” and any integer expressed in standard positional notation of base n, the radix point is implicitly to the right of all the digits. Therefore we start pairing on the right of the number and work leftward.

Generally, x is a multiple of t_ω2 if the total of all the base-n digit-pairs of x are clearly a multiple of t_ω2.

The omega-2 test is obscure and rarely practical; decimally it applies to 33 and 99. See this page for more on the omega-2 test.

8 | x: In quinary (base 5), we can tell the number x is a multiple of eight (written in quinary as “13”) if the sum of digit blocks (paired starting from the right) is clearly a multiple of 8. The number “4022” is a multiple of eight since “40” + “22” = “62”. (Note that “4022” = 8³ = decimal 512, and “62” is 6 fives and 2, which is decimal 32).

α₂ | x: the alpha-2 test

Main article: alpha-2. (Back to top ↑)

Consider α₂ = (n² + 1). We consider factors t_α2 | α₂ alpha-2 factors. These numbers are coprime to n. We may use the alternating sum applied to blocks of paired digits starting from the radix point and working leftward to determine whether t_α2 | x in base n. An example of the alternating sum applied to paired digits: for a number “12345”, we add (“1” + “45”) − (“23”), which in bases n > 7 is written “23”. In that number “12345” and any integer expressed in standard positional notation of base n, the radix point is implicitly to the right of all the digits. Therefore we start pairing on the right of the number and work leftward.

Generally, x is a multiple of t_α2 if the total of all the base-n digit-pairs of x are clearly a multiple of t_α2.

The alpha-2 test is a handy solution for 5 | x in bases n = 5m + 2 = {2, 3, 7, 8, 12, 13, 17, 18, …}. It is practical only in a few of these, since the rule requires memorization of the products of 5 to the hundred-like n². See this page for more on the alpha-2 test.

5 | x: In octal (base 8), we can tell the number x is a multiple of 5 if the alternating sum of digit blocks (paired starting from the right) is clearly a multiple of 5. The number “175” is a multiple of 5 since “75” − “1” = “74”. (Note that “175” = 5³ = decimal 125, and “74” is 7 eights and 4, which is decimal 60).

5 | x: In duodecimal (base 12), we can tell the number x is a multiple of 5 if the alternating sum of digit blocks (paired starting from the right) is clearly a multiple of 5. The number “14429025” is a multiple of 5 since (“42” + “25”) − (“14” + “90”) = “67” − “a4” = “39”. (Note that “14429025” = 5¹¹ = decimal 48828125, and “39” is 3 dozen 9, which is decimal 45).

 

It is clear from proofs in [2] that we can devise a divisibility test for any number k > 1 in base n > 1. We elect in this work not to consider tests that require memorizing lists of residues of perfect powers of n (mod k), since these tests do not seem to be the most easily-recalled and handy. These tests can be condensed as shown by using succinct notation such as {0 | 4, 2, 1} for 8 | x, or {1} for 3 | x. However succinct these are, it seems that most people do not connect with them, and that they are not widely known as they are not widely taught today.

Another class of divisibility test involving taking a block of b digits from the left or right and multiplying them by a residue h will be discussed later. These are clearly laid out in [3] but also appear in [2].

The right trim test

(Back to top ↑)

We can produce divisibility tests k | x for k coprime to n that merely require breaking the base-n expansion of x into two parts, separating the least significant or rightmost digit d from the rest of the digits D [4]. Given a positive or negative coefficient c, we interpret the digits as a new base-n number and perform the following operation:

D + c × d

For example, we use the following rule to determine if x is divisible by 7 in decimal. The number is a multiple of 7 if we double the last digit of x, then subtract the product from the decimal number formed by the remaining digits of x. Repeat as necessary. If the result is clearly divisible by 7, then so is x. The number 2401 is divisible by 7 since 240 − 2 = 238, 23 − 16 = 7 is clearly a multiple of 7. (The number 2401 is the fourth power of 7). Here the coefficient c = −2.

We can determine the coefficient c for k coprime to n by finding numbers 1 ≤ c ≤ n for which n⁻¹ mod k ≡ c. Recognizing that c is equivalent to −(k − c), we may choose a clement coefficient to make the rule simpler. For base n = 10 and k = 7, we may use c = +5 or −2.

We can split a block of b = 2 rightmost digits in much the same way as above. The coefficient is then derived by finding numbers 1 ≤ c ≤ n for which (n^b)⁻¹ mod k ≡ c.

The right trim test is an important source of 7 | x for bases n = 7m ± 2 or 3.

The left trim test

(Back to top ↑)

We can also produce divisibility tests k | x for k coprime to n that require breaking the base-n expansion of x into two parts, separating the most significant or leftmost digit d from the rest of the digits D. Given a positive or negative coefficient c, we interpret the digits as a new base-n number D and perform the following operation:

With x = (d × n^e) + D,
D + c × d × n^{(n − 2)}

Essentially, we apply c × d two places right of where the leftmost digit used to be. See [4] for more detail on this test.

Other tests

See [1, 4] for more about divisibility tests.

Compound tests

(Back to top ↑)

Divisibility tests can be written for composite numbers k that have more than a single prime divisor p (i.e, “little omega” ω(k) > 1), given divisibility tests for each of the prime power factors of k. Recall the prime power decomposition of k:

Let k = p₁^e1 × p₂^e2 × … × p_i^ei,
where p₁ < p₂ < … < p_i,

A prime power factor of k is simply one of the prime powers p^e that produce k. For instance we can express k = 120 = 2³ × 3 × 5, where 3, 5, and 8 are the prime power factors. If we have the divisibility tests 3 | x, 5 | x, and 8 | x, we have 60 | x. We cannot devise a test via any other factorization of 120, such as 10 × 12 or 4 × 5 × 6 as the factors must be mutually coprime.

Therefore, k = p₁^e1 × p₂^e2 × … × p_i^ei, given the tests for each of p₁^e1 | x, p₂^e2 | x, …, p_i^ei | x, we have the test k | x. In this work, k is said to inherit divisibility tests from each of its prime power factors.

For small composite k that have at least 2 distinct prime factors, it can be useful to discern the provenance of the divisibility tests that it inherits. For instance, we can say k = 6 in base n = 10 is an omega-regular inheritor (or simply omega inheritor), since 2 is a divisor of 10 and 3 | (10 − 1). The same number k = 6 in base n = 14 is an alpha-regular inheritor (or simply alpha inheritor), since 2 is a divisor of 14 and 3 | (14 + 1). In octal (base 8), the test for fifteen (octal “17”) combines 3 | x and 5 | x, the former is an alpha test, the latter is the alpha-2. Therefore it could be called an “alpha-2-alpha inheritor”. At some point the utility of such designations is lost.

The maximum number of sources for divisibility tests is the same as the number of distinct prime divisors of k, i.e., “little omega” ω(k). For prime k = p or perfect prime powers k = p^e, only a single divisibility test source applies. For k < 30, we may only have at most 2 sources for divisibility tests. More highly divisible k can have quite a number of divisibility tests, and the specification of the test k | x in terms of inheritance can seem like a boutique coffee order.

Opaque numbers k in base n

(Back to top ↑)

In this work, a number k is said to be “opaque” in base n if it lacks regular or neighbor tests for all of its prime power factors. In certain bases, the alpha-2 may furnish a workable method for 5 | x or 13 | x (among others); certain trim tests can furnish 7 | x in other bases. To be sure, if a number kproves important to society, k | x will find use. A decimal example of this applies to 7 | x appears in [1] in the Talmud. Such a test seems obscure to us today merely for the easy availability of computational power that makes division by 7 trivial and nullifies the need for 7 | x. In duodecimal (base 12), we would anticipate 5 | x not to be as paramount as 2 | x or to a much lesser extent 3 | x, but more important than decimal or duodecimal 7 | x. Therefore, the alpha-2 test that pertains to duodecimal 5 | x may be common knowledge, especially before the advent of convenient precision computation devices. The same could be said for octal 5 | x.

Popularity of divisibility tests

(Back to top ↑)

In examining a few elementary sites, we observe that the most commonly shown divisibility tests pertain to 2, 3 and 9, 4, 5, and 6, sometimes 8, 11, and 12 are included, less frequently 7 appears. The divisibility test for 10 is discussed at times; perhaps on account of its ease it might be left out of the most common tests. Other times it seems 10 appears merely for completion. It seems that the evenness test (2 | x) is essential, followed by that pertaining to 3 (6 and 9 by extension and combination), then 4, 5, and 10. The test for 8 is usually hard-going and many seem to resort to division, while a less-intuitive or memorable divisibility test for 7, known at least since the Talmud, has seemed to have suffered the same fate in the modern era. The objective of this site then is to describe similar practical k | x tests for base n.

Using the most common search service in 2019, we find that hits for the phrases “divisibility test for k”, “divisibility rules for k”, or “divisibility by k” a given number k tends to vary inversely with k. The last mentioned phrase is the most popular, always between 1 and 2 thousand hits. The exception is 2 | x, where the phrase “even and odd” has 354 million hits in mid-2019. Hence we see maybe purely on account of the nomenclature, that the evenness test is the very most basic divisibility test for most people; indeed the nomenclature itself might be a sign that the test is paramount.

  2: 639, 625, 1830, 354,000
  3: 716, 624, 1720.
  4: 692, 704, 1760
  5: 655, 604, 1750
  6: 596, 570, 1940
  7: 584, 559, 1650
  8: 574, 556, 1760
  9: 550, 523, 1780
10: 597, 599, 1920
11: 513, 534, 1570
12: 495, 517, 1560
13: 444, 466, 1240

(Back to top ↑)

References

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

[2] Divisibility Rules. MathsIsFun. Retrieved June 2019.

[3] Mike’s Math Club. Divisibility Rules Chart. (PDF). Retrieved July 2019.

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

[5] Michael De Vlieger, Quick Divisibility Tests for Small Numbers in Any Base, The Number Base (5 July 2019). Retrieved in July 2019.

[6] Ore 1948, Chapter 9, “Congruences”, pp. 226-8.

This page last modified Friday 5 July 2019.
Copyright © 2019 Michael De Vlieger