Testing for Divisibility

The crisp new dollar bill that I have just taken from my wallet bears the serial number 24598176. It's easy to tell that the number is exactly divisible by 2 but not by 5. Is it divisible by 3? by 4? by 11?

 
In a 1962 Scientific American article, Martin Gardner noted that during the 15th and 16th centuries in Renaissance Europe, the rules for checking whether one number is divisible by another without a remainder were widely known, particularly because of their usefulness in reducing large-number fractions to their lowest terms.

The advent of decimal arithmetic reduced the need for such tests. "Few people, including many mathematicians, know all the simple rules by which large numbers can be tested quickly for divisibility by numbers 1 through 12," Gardner remarked.

More recently, Eli Maor observed in an article on divisibility that, at one of his presentations, none of the teachers present appeared to know the quick divisibility test for 11.

Nowadays, in a world where calculators are ubiquitous, divisibility rules may seem little more than quaint relics of a distant past. Nonetheless, they can be handy for solving digital puzzles, reducing fractions, and as targets for algorithm development.

Here's a set of rules for numbers from 2 to 12.

2 A number is divisible by 2 if and only if its last digit is even (ending in 0, 2, 4, 6, and 8).

For example, because the final digit 6 is an even number, 24598176 is divisible by 2.

3 Sum the digits. If the result is more than one digit, sum again and continue until one digit remains. If the final digit (called the digital root of the number) is a multiple of 3 (3, 6, or 9), the number is divisible by 3. This also means that you can scramble the digits of any multiple of 3 and still have a number that is a multiple of 3.

For example, 2 + 4 + 5 + 9 + 8 + 1 + 7 + 6 = 42; 4 + 2 = 6. Because the digital root of 24598176 is 6, which is divisible by 3, the original number must be divisible by 3.

4 A number is divisible by 4 if and only if the number represented by the last two digits is a multiple of 4.

Because 76 is divisible by 4, 24598176 is divisible by 4.

5 A number is divisible by 5 if and only if its last digit is 0 or 5.

6 A number is divisible by 6 if and only if it is divisible by both 2 and 3 (that is, it's an even number divisible by 3).

The number 24598176 is divisible by both 2 and 3, so it must be divisible by 6.

7 Multiply the last digit of the number by 2. Subtract that product from the number obtained by deleting the last digit of the original number. Repeat the two steps as necessary. The original number is divisible by 7 if and only if the resulting number is divisible by 7.

For example, 6 ✕ 2 = 12; 2459817 − 12 = 2459805; 5 ✕ 2 = 10; 245980 − 10 = 245970; 0 ✕ 2 = 0; 24597 − 0 = 24597; 7 ✕ 2 = 14; 2459 − 14 = 2445; 5 ✕ 2 = 10; 244 − 10 = 234; 4 ✕ 2 = 8; 23 − 8 = 15. Because 15 is not divisible by 7, neither is 24598176.

8 A number is divisible by 8 if the number represented by its last three digits is a multiple of 8.

Because 176 is divisible by 8, 24598176 is divisible by 8.

9 A number is divisible by 9 if and only if it has a digital root of 9.

For example, because the digital root of 24598176 is 6 (see 3, above), the number is not divisible by 9.

10 A number is divisible by 10 if and only if it ends in 0.

11 Take the digits from right to left, alternately subtracting and adding. The original number is divisible by 11 if and only if the resulting number is divisible by 11. (Assume that 0 is divisible by 11.)

For example, 6 − 7 + 1 − 8 + 9 − 5 + 4 − 2 = −2. Because −2 is not divisible by 11, 24598176 is not divisible by 11.

12 A number is divisible by 12 if and only if it is divisible by both 3 and 4.

The number 24598176 is divisible by both 3 and 4, so it must be divisible by 12.

In the case of 7, the rule is sufficiently complicated that it takes nearly as much effort to check for divisibility as it would take to perform the division operation itself. Indeed, dozens of algorithms for testing for 7 have been devised over the years, but none of them represents a significant time-saver.

In the 2002 article "Divisibility: A Problem Solving Approach Through Generalizing and Specializing," Rina Zazkis described a student investigation of how one algorithm for testing for 7 (the one mentioned above) could be generalized to other prime numbers.

Surprisingly, the same algorithm can be applied to determine divisibility by 3. For 24598176, the resulting number is 15 (see 7, above), which is divisible by 3.

Variants of this recipe, which Zazkis described as a "trimming" algorithm, work for other prime numbers.

19 Multiply the last digit of the number by 2. Add that product to the number obtained by deleting the last digit of the original number. Repeat the two steps as necessary. The original number is divisible by 19 if and only if the resulting number is divisible by 19.

For example, 6 ✕ 2 = 12; 2459817 + 12 = 2459829; 9 ✕ 2 = 18; 245982 + 18 = 246000; 0 ✕ 2 = 0; 24600 + 0 = 24600; 0 ✕ 2 = 0; 2460 + 0 = 2460; 0 ✕ 2 = 0; 246 + 0 = 246; 6 ✕ 2 = 12; 24 + 12 = 36. Because 36 is not divisible by 19; the original number is not divisible by 19.

It's possible to devise a divisibility rule based on some sort of trimming algorithm for any prime, p, except 2 and 5. "The existence of a trimming algorithm for p depends on the existence of a multiple of p which is larger by 1 or smaller by 1 than a multiple of 10," Zazkis noted.

Can a similar algorithm be used to determine divisibility by a composite number? Are there other algorithms that can be generalized to work for primes?

The realm of divisibility tests has all sorts of avenues for further investigation and algorithm development.

Originally posted August 19, 2002