This site is supported by donations to The OEIS Foundation.

# Divisibility tests

(Redirected from Divisibility test)

A divisibility test for a given integer ${\displaystyle n}$ determines whether an integer ${\displaystyle m}$ is divisible by ${\displaystyle n}$ without having to compute ${\displaystyle {\frac {m}{n}}}$ by examining the base ${\displaystyle b}$ digits of ${\displaystyle m}$.

1. Given an even base ${\displaystyle b}$, ${\displaystyle m}$ is divisible by 2 if the least significant digit of ${\displaystyle m}$ is 0, 2, 4, ... or ${\displaystyle b-2}$.
2. Given ${\displaystyle b\equiv 1\mod 3}$, ${\displaystyle m}$ is divisible by 3 if the digital root of ${\displaystyle m}$ is 3, 6, 9, ... ${\displaystyle b-1}$.
3. If ${\displaystyle b}$ is a multiple of 4, then it is enough to check if the least significant digit of ${\displaystyle m}$ is 0, 4, 8, ... or ${\displaystyle b-4}$. But if ${\displaystyle b}$ is even but not a multiple of 4 (singly even), then one must look at the two least significant digits to see if they are 00, 04, 08, 12, 16, ... or ${\displaystyle b^{2}-4}$ (this is because ${\displaystyle b^{2}}$ then is a multiple of 4).
4. The divisibility test for 5 in base 10 is greatly simplified by the fact that the base, 10, is twice 5. Therefore, all we need to determine if an integer is divisible by 5 is to is look at the least significant digit of the base 10 representation to see if it is 0 or 5.
5. In the case of 6 we can use a "composite" divisibility test: if ${\displaystyle m}$ passes the tests for 2 and for 3, then it is divisible by 6.
6. The divisibility tests for 7 in base 10 are all rather convoluted. One test involves doubling the least significant digit, subtracting that from the concatenation of the other digits, and repeating the procedure until arriving at 7, 0 or –7 (in which case ${\displaystyle m}$ is divisible by 7), or arriving at –6, ... –1, 1, ... 6, in which case it is not divisible by 7. For example: 1729 -> 172 – 18 = 154 -> 15 – 8 = 7, so 1729 is divisible by 7; 225 -> 22 – 10 = 12 -> 1 – 4 = –3, so 225 is not divisible by 7. It seems it would be much easier to just go ahead and compute ${\displaystyle {\frac {m}{7}}}$.
7. If ${\displaystyle b}$ is a multiple of 8, then it is enough to check if the least significant digit of ${\displaystyle m}$ is 0, 8, G, ... or ${\displaystyle b-8}$. But if ${\displaystyle b}$ is even but not a multiple of 8, or for that matter, of 4, then one must look at the three least significant digits to see if they are 000, 004, 008, 012, 016, ... or ${\displaystyle b^{3}-8}$ (this is because ${\displaystyle b^{3}}$ then is a multiple of 8).
8. Given ${\displaystyle b\equiv 1\mod 9}$, ${\displaystyle m}$ is divisible by 9 if the digital root of ${\displaystyle m}$ is 9, ... ${\displaystyle b-1}$.
9. ${\displaystyle m}$ is divisible by ${\displaystyle b}$ if the least significant digit of ${\displaystyle m}$ is 0.
10. If ${\displaystyle n=b+1}$, then ${\displaystyle m}$ is divisible by ${\displaystyle n}$ if the sum of the even-indexed digits minus the sum of the odd-indexed digits if a multiple of ${\displaystyle n}$. For example, 1727 is a multiple of 11 since (1 + 2) – (7 + 7) = –11. With 1729 we see that (1 + 2) – (7 + 9) = –13.
11. For 12 we once again give a composite divisibility test: if ${\displaystyle m}$ is divisible by 3 and 4.