In general, an integer  is divisible by  iff the digit sum  is divisible by .

Write a positive decimal integer  out digit by digit in the form . The following rules then determine if  is divisible by another number by examining the congruence properties of its digits. In congruence notation,  means that the remainder when  is divided by a modulus  is . (Note that it is always true that  for any base.)

1. All integers are divisible by 1.

2. , so  for . Therefore, if the last digit  is divisible by 2 (i.e., is even), then so is .

3. , , , ...,  (mod 3). Therefore, if the digit sum  is divisible by 3, so is  (Wells 1986, p. 48). In general, if the sum of any permutation of the digits of  in any order is divisible by 3, then so is .

4a. , , ...,  (mod 4). So if the last two digits are divisible by 4, then so is .

4b. If  is, then so is .

5. , so  for . Therefore, if the last digit  is divisible by 5 (i.e., is 5 or 0), then so is .

6a. If  is divisible by 3 and is even, then  is also divisible by 6.

6b. , , ...,  (mod 6). Therefore, if  is divisible by 6, so is . The final number can then, of course, be further reduced using the same procedure.

7a. , , , , ,  (mod 7), and the sequence then repeats. Therefore, if  is divisible by 7, so is . This method was found by Pascal.

7b. An alternate test proceeds by multiplying  by 3 and adding to , then repeating the procedure up through . The final number can then, of course, be further reduced using the same procedure. If the result is divisible by 7, then so is the original number (Wells 1986, p. 70).

7c. A third test multiplies  by 5 and adds it to , proceeding up through . The final number can then, of course, be further reduced using the same procedure. If the result is divisible by 7, then so is the original number (Wells 1986, p. 70).

7d. Given a number, form two numbers  and  such that  consists of all digits of the number except the last (units) digit and  is the last digit. Compute  and repeat the procedure. Then the original number is divisible by 7 iff the number in the last step is divisible by 7.

8. , , , ...,  (mod 8). Therefore, if the last three digits are divisible by 8, more specifically if  is, then so is  (Wells 1986, p. 72).

9. (Rule of nines). , , , ...,  (mod 9). Therefore, if the digit sum  is divisible by 9, so is  (Wells 1986, p. 74).

10.  (mod 10), so if the last digit is 0, then  is divisible by 10.

11. , , , , ... (mod 11). Therefore, if  is divisible by 11, then so is .

12. , , , ... (mod 12). Therefore, if  is divisible by 12, then so is . Divisibility by 12 can also be checked by seeing if  is divisible by 3 and 4.

13. , , , , ,  (mod 13), and the pattern repeats. Therefore, if  is divisible by 13, so is .

For additional tests for 13, see Gardner (1991).

An interesting piece of English language trivia is that the word "indivisibilities" has more "i"s (in fact, seven of them) than any other common word. (Other words with seven i's include, honorificabilitudinitatibus, indistinguishabilities, indivisibilities, and supercalifragilisticexpialidocious. Phrases with eight i's include "Illinois fighting Illini" and "infinite divisibility." The English word with the most possible i's is floccinaucinihilipilification (nine i's), where "floccinaucinihilipilification" means "the action or habit of estimating as worthless.")

REFERENCES:

Burton, D. M. "Special Divisibility Tests." §4.3 in Elementary Number Theory, 4th ed. Boston, MA: Allyn and Bacon, pp. 89-96, 1989.

Dickson, L. E. History of the Theory of Numbers, Vol. 1: Divisibility and Primality. New York: Dover, pp. 337-346, 2005.

Gardner, M. "Tests of Divisibility." Ch. 14 in The Unexpected Hanging and Other Mathematical Diversions. Chicago, IL: Chicago University Press, pp. 160-169, 1991.

Wells, D. The Penguin Dictionary of Curious and Interesting Numbers. Middlesex, England: Penguin Books, p. 48, 1986.