Divisibility Tests

Write a positive decimal integer $a$ out digit by digit in the form $a_n \ldots a_3 a_2 a_1 a_0$. The following rules then determine if $a$ is divisible by another number by examining the Congruence properties of its digits.

2. $10^1\equiv 0\ \left({{\rm mod\ } {2}}\right)$, so $10^n\equiv 0\ \left({{\rm mod\ } {2}}\right)$ for $n\geq 1$. Therefore, if the last digit $a_0$ is divisible by 2 (i.e., is Even), then so is $a$.

3. $10^0\equiv 1$, $10^1\equiv 1$, $10^2\equiv 1$, ..., $10^n\equiv 1$ (mod 3). Therefore, if $\sum_{i=0}^n a_i$ is divisible by 3, so is $a$.

4. $10^1\equiv 2$, $10^2\equiv 0$, ...$10^n\equiv 0$ (mod 4). So if the last two digits are divisible by 4, more specifically if $r\equiv a_0+2a_1$ is, then so is $a$.

5. $10^1\equiv 0\ \left({{\rm mod\ } {5}}\right)$, so $10^n\equiv 0\ \left({{\rm mod\ } {5}}\right)$ for $n\geq 1$. Therefore, if the last digit $a_0$ is divisible by 5 (i.e., is 5 or 0), then so is $a_0$.

6. $10^1\equiv -2$, $10^2\equiv -2$, ..., $10^n\equiv -2$ (mod 6). Therefore, if $r\equiv a_0-2\sum_{i=1}^n a_i$ is divisible by 6, so is $a$. A simpler rule states that if $a$ is divisible by 3 and is Even, then $a$ is also divisible by 6.

7. $10^1\equiv 3$, $10^2\equiv 2$, $10^3\equiv -1$, $10^4\equiv -3$, $10^5 \equiv -2$, $10^6\equiv 1$ (mod 7), and the sequence then repeats. Therefore, if $r\equiv (a_0+3a_1+2a_2 -a_3-3a_4-2a_5)+(a_6+3a_7+\ldots)+\ldots$ is divisible by 7, so is $a$.

8. $10^1\equiv 2$, $10^2\equiv 4$, $10^3 \equiv 0$, ..., $10^n\equiv 0$ (mod 8). Therefore, if the last three digits are divisible by 8, more specifically if $r\equiv a_0+2a_1+4a_2$ is, then so is $a$.

9. $10^0\equiv 1$, $10^1\equiv 1$, $10^2\equiv 1$, ..., $10^n\equiv 1$ (mod 9). Therefore, if $\sum_{i=0}^n a_i$ is divisible by 9, so is $a$.

10. $10^1\equiv 0$ (mod 10), so if the last digit is 0, then $a$ is divisible by 10.

11. $10^1\equiv -1$, $10^2\equiv 1$, $10^3\equiv -1$, $10^4\equiv 1$, ... (mod 11). Therefore, if $r\equiv a_0-a_1+a_2-a_3+\ldots$ is divisible by 11, then so is $a$.

12. $10^1\equiv -2$, $10^2\equiv 4$, $10^3\equiv 4$, ... (mod 12). Therefore, if $r\equiv a_0-2a_1+4(a_2+a_3+\ldots)$ is divisible by 12, then so is $a$. Divisibility by 12 can also be checked by seeing if $a$ is divisible by 3 and 4.

13. $10^1\equiv -3$, $10^2\equiv -4$, $10^3\equiv -1$, $10^4\equiv 3$, $10^5\equiv 4$, $10^6\equiv 1$ (mod 13), and the pattern repeats. Therefore, if $r\equiv (a_0-3a_1-4a_2-a_3+3a_4+4a_5)+(a_6-3a_7+\ldots)+\ldots$ is divisible by 13, so is $a$.

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

References

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

Gardner, M. Ch. 14 in The Unexpected Hanging and Other Mathematical Diversions. Chicago, IL: Chicago University Press, 1991.