Divisibility Tests

How Divisibility Tests Work

Recall from Base Number Systems that every positive integer $N$ has a unique base 10 digit string,

$$N=(d_k{d}_{k-1}\cdots d_1{d}_0{)}_{10}=d_k\times 10^k+d_{k-1}\times 10^{k-1}+\cdots +d_1\times 10+d_0,$$

where each digit $d_i\in \{0,1,\dots ,9\}$. Also recall that congruences respect addition and multiplication; if we reduce everything mod $n$, the digits stay exactly where they are and only the powers of $10$ change. This gives us the master congruence that every test in this lecture falls out of:

$$\boxed{N\equiv d_k\left(10^k\mathrm{mod}n\right)+\cdots +d_1\left(10\mathrm{mod}n\right)+d_0(\mathrm{mod}n).}$$

Basically, to test divisibility by $n$ we never need to actually divide by $n$; we only need to know how the powers of $10$ behave mod $n$. There are three behaviours worth knowing:

• $10^i\equiv 0(\mathrm{mod}n)$ from some point onwards (this happens exactly when $n$ divides a power of $10$, i.e. $n=2^a{5}^b$); then only the last few digits matter.
• $10\equiv 1(\mathrm{mod}n)$ (this is $n=3$ or $9$); then every power of $10$ is $1$ and we just sum the digits.
• $10\equiv -1(\mathrm{mod}n)$ (this is $n=11$); then the powers alternate between $1$ and $-1$ and we alternately add and subtract digits.

For everything else (like $7$ and $13$), the powers of $10$ cycle through junk values, so we cheat: we multiply the number by a carefully chosen constant first so that a nice pattern appears. Divisibility tests like these matter because they replace division (which is expensive to do in your head) with addition, subtraction and truncation, and they let you sniff out prime factorisations quickly.

Divisibility by Powers of 2 and 5

Basically, $2$ and $5$ are the prime factors of $10$, so high enough powers of $10$ absorb any power of $2$ or $5$; everything past the last $k$ digits is invisible mod $2^k$ and mod $5^k$, so you can just throw it away.

Proof. Split $N$ into the part before and after its last $k$ digits;

$$\begin{array}{rl}N& =(d_j\cdots d_k{)}_{10}\times 10^k+(d_{k-1}\cdots d_1{d}_0{)}_{10}\\ & =M\times 10^k+L,\text{ where }L\text{ is the number formed by the last }k\text{ digits}.\end{array}$$

Since $10^k=2^k{5}^k$, we have $2^k\mid 10^k$, i.e. $10^k\equiv 0(\mathrm{mod}{2}^k)$. Reducing mod $2^k$,

$$\begin{array}{rl}N& \equiv M\times 0+L(\mathrm{mod}{2}^k),\text{ (as }10^k\equiv 0\text{)}\\ & \equiv L(\mathrm{mod}{2}^k).\end{array}$$

Therefore $2^k\mid N$ if and only if $2^k\mid L$. The exact same argument with $5^k\mid 10^k$ proves the second lemma. $■$

The small cases are the ones you use constantly:

• $2$: last digit is even,
• $4$: last two digits divisible by $4$,
• $8$: last three digits divisible by $8$,
• $5$: last digit is $0$ or $5$,
• $10$: last digit is $0$ (since $10=2\times 5$, this is really the $2$ test and the $5$ test at once).

The tests for 2, 5 and 10 are basically primary school stuff so I'm not gonna dwell on them.

Example. Which powers of $2$ and $5$ divide $123450$?
Work through the last digits one layer at a time;

$$\begin{array}{rlrl}\text{last digit: }& 0,& & \text{so }2\mid 123450\text{ and }5\mid 123450,\\ \text{last two digits: }& 50=4(12)+2,& & \text{so }4\nmid 123450,\\ & 50=25(2),& & \text{so }25\mid 123450,\\ \text{last three digits: }& 450=125(3)+75,& & \text{so }125\nmid 123450.\end{array}$$

Notice how once $4$ fails there is no point testing $8$; if $8\mid N$ then $4\mid N$, so the powers of $2$ stop dead at the first failure. Therefore, the only powers dividing $123450$ are $2^1$ and $5^1,5^2$; in fact $123450=2\times 3\times 5^2\times 823$.

Example. Find the largest power of $2$ dividing $2,345,678,000$.
The lemma works for any $k$, not just the $k\le 3$ in the standard table; we keep grabbing one more digit until the test fails.

$$\begin{array}{rlrl}\text{last three digits: }000& =0,& & \text{so }8\mid N\text{ (every number divides }0\text{)},\\ \text{last four digits: }8000& =16(500),& & \text{so }16\mid N,\\ \text{last five digits: }78000& =32(2437)+16,& & \text{so }32\nmid N.\end{array}$$

Therefore, the largest power of $2$ dividing $2,345,678,000$ is $2^4=16$. It is important to note that trailing zeros hand you factors for free: three trailing zeros means $10^3=2^3{5}^3$ divides the number immediately, and you only have to do real work from the fourth digit onwards.

Divisibility by 3 and 9

This is the famous digit-sum test, and the reason it works is one line of modular arithmetic: $10\equiv 1(\mathrm{mod}9)$, so every power of $10$ is congruent to $1$, and each digit just contributes itself.

Proof. Let $N=(d_k\cdots d_1{d}_0{)}_{10}$. Since $10\equiv 1(\mathrm{mod}9)$, we have $10^i\equiv 1^i=1(\mathrm{mod}9)$ for every $i$ (congruences respect multiplication, so we may raise both sides to the $i$​th power). Then

$$\begin{array}{rl}N& =d_k\times 10^k+\cdots +d_1\times 10+d_0\\ & \equiv d_k\times 1+\cdots +d_1\times 1+d_0(\mathrm{mod}9),\text{ (replacing each }10^i\text{ by }1\text{)}\\ & \equiv d_k+d_{k-1}+\cdots +d_1+d_0(\mathrm{mod}9).\end{array}$$

So $N$ is congruent to its own digit sum mod $9$; in particular $9\mid N$ if and only if $9$ divides the digit sum. Since $10\equiv 1(\mathrm{mod}3)$ as well, the identical argument works mod $3$. $■$

Notice that the proof gives us something strictly stronger than the lemma;

$$\boxed{N\equiv d_k+d_{k-1}+\cdots +d_1+d_0(\mathrm{mod}9)\text{ and }(\mathrm{mod}3).}$$

The digit sum doesn't just tell you whether $9\mid N$; it tells you the actual remainder. You can also iterate; if the digit sum is still big, take the digit sum of the digit sum, since the congruence keeps holding.

Example. Which of $123450$ and $12345678$ are divisible by $3$ or by $9$?
For $123450$,

$$\begin{array}{rl}1+2+3+4+5+0& =15\\ & =3(5),\end{array}$$

so $3\mid 123450$, but $9\nmid 15$ so $9\nmid 123450$; in fact $123450\equiv 15\equiv 6(\mathrm{mod}9)$.
For $12345678$,

$$\begin{array}{rl}1+2+3+4+5+6+7+8& =36\\ & =9(4),\end{array}$$

so $9\mid 12345678$, and hence automatically $3\mid 12345678$ too. Therefore, $123450$ is divisible by $3$ only, while $12345678$ is divisible by both $3$ and $9$.

Casting Out Nines

Because $N$ is congruent to its digit sum mod $9$ (not just "divisible iff divisible"), we can use the digit-sum lemma to sanity-check arithmetic: any correct equation in $\mathbb{Z}$ must still be a correct congruence in ${\mathbb{Z}}_9$, and digit sums make working mod $9$ nearly free. This trick is called casting out nines.

Example. A friend claims that $6437+2895=9342$. Check the claim by casting out nines.
Reduce everything mod $9$ using digit sums;

$$\begin{array}{rl}6437& \equiv 6+4+3+7=20\equiv 2(\mathrm{mod}9),\\ 2895& \equiv 2+8+9+5=24\equiv 6(\mathrm{mod}9),\\ 6437+2895& \equiv 2+6=8(\mathrm{mod}9),\\ 9342& \equiv 9+3+4+2=18\equiv 0(\mathrm{mod}9).\end{array}$$

Since $8\not\equiv 0(\mathrm{mod}9)$, the claimed answer is wrong without us ever doing the addition. Therefore, the sum cannot be $9342$; the true answer is $9332$, which indeed satisfies $9+3+3+2=17\equiv 8(\mathrm{mod}9)$.

It is important to remember that casting out nines can only ever prove an answer wrong; a passed check does not prove the answer right, and it will never catch a mistake that swaps two digits, because swapping digits does not change the digit sum. For digit swaps you need the mod $11$ test below, where position actually matters.

Divisibility by 11

The mechanism is the mirror image of the digit-sum test: this time $10\equiv -1(\mathrm{mod}11)$, so the powers of $10$ flip sign at every position, i.e. $10^i\equiv (-1{)}^i(\mathrm{mod}11)$.

Proof. Let $N=(d_k\cdots d_1{d}_0{)}_{10}$. Since $10\equiv -1(\mathrm{mod}11)$, we have $10^i\equiv (-1{)}^i(\mathrm{mod}11)$, so

$$\begin{array}{rl}N& =d_k\times 10^k+\cdots +d_2\times 10^2+d_1\times 10+d_0\\ & \equiv d_k(-1{)}^k+\cdots +d_2-d_1+d_0(\mathrm{mod}11)\\ & \equiv d_0-d_1+d_2-d_3+\cdots (\mathrm{mod}11).\end{array}$$

Hence $11\mid N$ if and only if $11$ divides the alternating sum of the digits. $■$

Basically, the even-position digits (units, hundreds, ...) count positively and the odd-position digits (tens, thousands, ...) count negatively. If you start the alternation from the leftmost digit instead you might get the negative of this sum, which makes no difference to divisibility, but if you want the actual remainder mod 11 you must start from the units digit with a plus sign.

Example. Which of $123450$ and $1234321$ are divisible by $11$?
For $123450$, starting from the units digit,

$$\begin{array}{rl}0-5+4-3+2-1& =-3,\end{array}$$

and $11\nmid -3$, so $11\nmid 123450$ (in fact $123450\equiv -3\equiv 8(\mathrm{mod}11)$).
For $1234321$,

$$\begin{array}{rl}1-2+3-4+3-2+1& =0,\end{array}$$

and every number divides $0$, so $11\mid 1234321$. Therefore, only $1234321$ is divisible by $11$; unsurprising once you notice $1234321=1111^2$ and $11\mid 1111$.

Catching Digit Swaps

Here is the follow-up to casting out nines: transposition errors are invisible mod $9$ but visible mod $11$, since the alternating sum cares which position each digit sits in. Checking mod $9$ and mod $11$ together is a genuinely strong error check.

Example. A friend claims that $8734\times 56=489140$. Check the claim mod $9$ and mod $11$.
First cast out nines;

$$\begin{array}{rl}8734& \equiv 8+7+3+4=22\equiv 4(\mathrm{mod}9),\\ 56& \equiv 5+6=11\equiv 2(\mathrm{mod}9),\\ 8734\times 56& \equiv 4\times 2=8(\mathrm{mod}9),\\ 489140& \equiv 4+8+9+1+4+0=26\equiv 8(\mathrm{mod}9).\end{array}$$

The mod $9$ check passes, so casting out nines sees nothing wrong. Now check mod $11$ with alternating sums (units digit first);

$$\begin{array}{rl}8734& \equiv 4-3+7-8=0(\mathrm{mod}11),\\ 8734\times 56& \equiv 0\times 56=0(\mathrm{mod}11),\\ 489140& \equiv 0-4+1-9+8-4=-8\equiv 3(\mathrm{mod}11).\end{array}$$

Since $3\not\equiv 0(\mathrm{mod}11)$, the claim is false. Therefore, the product cannot be $489140$; the true answer is $489104$ (the last two digits were swapped), and you can check its alternating sum is $4-0+1-9+8-4=0$ as required.

Divisibility by 7

In symbols: write $N=10a+b$ where $b$ is the last digit and $a$ is the rest of the number; then $7\mid N$ if and only if $7\mid a-2b$. You apply this repeatedly, shrinking the number by one digit each time, until it is small enough to eyeball.

Why does this work? The powers of $10$ mod $7$ cycle through $3,2,6,4,5,1$ — no nice pattern — so no digit-sum-style test exists. The trick from the lectures: look for a small multiple of $7$ that sits next to a multiple of $10$. We find $21=2\times 10+1$, so $20\equiv -1(\mathrm{mod}7)$, and multiplying $N$ by $2$ makes everything collapse.

Proof. Let $N=10a+b$. Multiplying by $2$,

$$\begin{array}{rl}2N& =20a+2b\\ & \equiv (-1)a+2b(\mathrm{mod}7),\text{ (as }20=21-1\equiv -1\text{)}\\ & \equiv -(a-2b)(\mathrm{mod}7).\end{array}$$

Since $\gcd (2,7)=1$, multiplying by $2$ does not create or destroy factors of $7$; hence $7\mid N⟺7\mid 2N⟺7\mid a-2b$. $■$

Example. Which of $12345$ and $97531$ are divisible by $7$?
For $12345$, repeatedly remove the last digit and subtract twice it;

$$\begin{array}{rl}1234-2(5)& =1224,\\ 122-2(4)& =114,\\ 11-2(4)& =3.\end{array}$$

Since $7\nmid 3$, we conclude $7\nmid 12345$.
For $97531$,

$$\begin{array}{rl}9753-2(1)& =9751,\\ 975-2(1)& =973,\\ 97-2(3)& =91,\\ 9-2(1)& =7.\end{array}$$

Since $7\mid 7$, we conclude $7\mid 97531$ (indeed $97531=7\times 13933$). Therefore, only $97531$ is divisible by $7$. You could also have stopped at $91$ if you recognised $91=7\times 13$; stop as soon as you can see the answer.

Unlike the digit-sum test, this test does not preserve remainders; it only preserves whether the remainder is zero. For example, take $N=16$: the test gives $1-2(6)=-11\equiv 3(\mathrm{mod}7)$, but $16\equiv 2(\mathrm{mod}7)$. The culprit is that we multiplied by $2$ along the way, which scrambles every nonzero residue while fixing $0$. So use this for yes/no questions only; if an exam question wants $N\mathrm{mod}7$, do it directly.

Divisibility by 13

Same idea as for $7$: we hunt for a small multiple of $13$ adjacent to a multiple of $10$, and this time $39=4\times 10-1$ works, giving $40\equiv 1(\mathrm{mod}13)$.

Proof. Let $N=10a+b$. Multiplying by $4$,

$$\begin{array}{rl}4N& =40a+4b\\ & \equiv a+4b(\mathrm{mod}13),\text{ (as }40=39+1\equiv 1\text{)}.\end{array}$$

Since $\gcd (4,13)=1$, we get $13\mid N⟺13\mid 4N⟺13\mid a+4b$. $■$

Example. Which of $12345$ and $12389$ are divisible by $13$?
For $12345$, repeatedly remove the last digit and add four times it;

$$\begin{array}{rl}1234+4(5)& =1254,\\ 125+4(4)& =141,\\ 14+4(1)& =18.\end{array}$$

Since $13\nmid 18$, we conclude $13\nmid 12345$.
For $12389$,

$$\begin{array}{rl}1238+4(9)& =1274,\\ 127+4(4)& =143,\\ 14+4(3)& =26.\end{array}$$

Since $26=13\times 2$, we conclude $13\mid 12389$ (indeed $12389=13\times 953$). Therefore, only $12389$ is divisible by $13$. The same remainder warning applies here: because we multiplied by $4$, the final number $26$ tells you nothing about $N\mathrm{mod}13$ beyond the fact that it is $0$.

Tests for Composite Numbers

What about $6$, $12$, $15$, and friends? We do not need new tests; we split the modulus into pieces we already know how to test, provided the pieces share no common factor.

Proof. ($\Rightarrow$) If $mn\mid N$, then since $m\mid mn$ and $n\mid mn$, transitivity of divisibility (Lemma 1.2 in Divisibility and Primes) gives $m\mid N$ and $n\mid N$.
($\Leftarrow$) Suppose $m\mid N$ and $n\mid N$, so $N=mk$ for some $k\in \mathbb{Z}$. Then $n\mid mk$, and since $\gcd (n,m)=1$, $n$ has no factors in common with $m$, so $n$ must divide $k$; write $k=n\ell$. Then $N=mn\ell$, so $mn\mid N$. $■$

Basically, a number is divisible by $6$ exactly when it passes the $2$ test and the $3$ test, and divisible by $12$ exactly when it passes the $4$ test and the $3$ test.

You must split into coprime pieces; being divisible by $4$ and by $6$ does not make a number divisible by $24$, because $\gcd (4,6)=2\ne 1$. For example, $612$ is divisible by $4$ (last two digits $12$) and by $6$ (even, digit sum $9$), yet $612=24\times 25+12$, so $24\nmid 612$. The correct split is $24=8\times 3$; the last three digits give $612=8\times 76+4$, so the $8$ test fails and $24\nmid 612$, as expected.

Example. Is $123450$ divisible by $6$? Is $12345678$ divisible by $12$?
For $6=2\times 3$ (coprime pieces): $123450$ ends in $0$, so $2\mid 123450$; its digit sum is $15$, so $3\mid 123450$. Both tests pass, therefore $6\mid 123450$.
For $12=4\times 3$ (coprime pieces): the digit sum of $12345678$ is $36$, so $3\mid 12345678$; but the last two digits give

$$\begin{array}{rl}78& =4(19)+2,\end{array}$$

so $4\nmid 12345678$. Therefore $12\nmid 12345678$, even though it is divisible by $9$; one failed piece is enough to kill the whole test.

Example. Is $40,740,711$ divisible by $33$? By $99$?
Since $33=3\times 11$ and $\gcd (3,11)=1$, we run the $3$ test and the $11$ test and combine them using the coprime factor proposition.
Digit sum:

$$\begin{array}{rl}4+0+7+4+0+7+1+1& =24\\ & =3(8),\end{array}$$

so $3\mid 40740711$, but $9\nmid 24$ so $9\nmid 40740711$.
Alternating sum (units digit first):

$$\begin{array}{rl}1-1+7-0+4-7+0-4& =0,\end{array}$$

so $11\mid 40740711$. Both the $3$ test and $11$ test pass, therefore $33\mid 40740711$ (in fact $40740711=33\times 1234567$). However $99=9\times 11$ needs the $9$ test to pass, and it fails; therefore $99\nmid 40740711$. Notice how one digit sum and one alternating sum settled divisibility by $3,9,11,33$ and $99$ all at once; this is why you factorise the modulus first instead of long-dividing.

Designing Your Own Tests

The tests for $7$ and $13$ came from one recipe, and the lecture notes point out it generalises: for any prime $p$ other than $2$ and $5$, look for a small multiple of $p$ that is one more or one less than a multiple of $10$. We can package the whole recipe as a proposition.

Proof. Multiply $N$ by $m$;

$$\begin{array}{rl}mN& =(10m)a+mb\\ & \equiv \epsilon a+mb(\mathrm{mod}p),\text{ (as }10m\equiv \epsilon \text{)}\\ & \equiv \epsilon (a+\epsilon mb)(\mathrm{mod}p),\text{ (as }{\epsilon }^2=1\text{)}.\end{array}$$

Now $p\nmid m$ (otherwise $10m\equiv 0\not\equiv \pm 1(\mathrm{mod}p)$), so multiplying by $m$ preserves divisibility by $p$; and multiplying by $\epsilon =\pm 1$ obviously does too. Hence $p\mid N⟺p\mid mN⟺p\mid a+\epsilon mb$. $■$

Sanity check against what we already have: for $p=7$, $21\equiv 0$ gives $10(2)\equiv -1$, so $m=2$, $\epsilon =-1$ and the test is $a-2b$; for $p=13$, $39\equiv 0$ gives $10(4)\equiv 1$, so $m=4$, $\epsilon =1$ and the test is $a+4b$. Both match the lemmas above.

Example. Build a truncation test for $17$, and use it to decide whether $17\mid 2023$.
We want a multiple of $17$ next to a multiple of $10$; $51=3\times 17$ works, since $51=50+1$ gives

$$\begin{array}{rl}50& \equiv -1(\mathrm{mod}17)\\ 10(5)& \equiv -1(\mathrm{mod}17),\end{array}$$

so $m=5$, $\epsilon =-1$: remove the last digit and subtract 5 times it. Applying this to $2023$;

$$\begin{array}{rl}202-5(3)& =187,\\ 18-5(7)& =-17.\end{array}$$

Since $17\mid -17$, we conclude $17\mid 2023$. Therefore $2023$ is divisible by $17$; indeed $2023=7\times 17^2$. (Negative outputs are fine; divisibility doesn't care about sign.)

Example. Build a truncation test for $19$, and use it to decide whether $19\mid 2261$.
Here $19$ itself is one less than $20$, so

$$\begin{array}{rl}20& \equiv 1(\mathrm{mod}19)\\ 10(2)& \equiv 1(\mathrm{mod}19),\end{array}$$

giving $m=2$, $\epsilon =1$: remove the last digit and add 2 times it. Applying this to $2261$;

$$\begin{array}{rl}226+2(1)& =228,\\ 22+2(8)& =38.\end{array}$$

Since $38=19\times 2$, we conclude $19\mid 2261$. Therefore $2261$ is divisible by $19$; indeed $2261=19\times 119$.

Block Tests

The digit-sum idea also generalises: instead of asking how $10$ behaves mod $p$, ask how $10^k$ behaves for small $k$. If $10^k\equiv 1(\mathrm{mod}p)$, then chopping $N$ into blocks of $k$ digits (from the right) and summing the blocks preserves the value of $N$ mod $p$ — exactly the digit-sum proof with $10^k$ playing the role of $10$. And because we never multiply by anything, block tests preserve remainders, unlike the truncation tests.

Example. Build a test for $37$, and use it to decide whether $37\mid 456765$.
Notice $999=27\times 37$, so

$$\begin{array}{rl}10^3& \equiv 1(\mathrm{mod}37),\end{array}$$

which means every 3-digit block contributes itself: chop into blocks of three and add. For $456765$ the blocks are $456$ and $765$;

$$\begin{array}{rl}456+765& =1221\\ & =37(33).\end{array}$$

Since $37\mid 1221$, we conclude $37\mid 456765$ (indeed $456765=37\times 12345$). Therefore $456765$ is divisible by $37$. As a bonus, the same fact $999=27\times 37$ gives an identical 3-digit block test for $27$; here $1221=27\times 45+6$, so $27\nmid 456765$.

Example. Use $1001=7\times 11\times 13$ to test $12345$ for divisibility by $7$, $11$ and $13$ simultaneously.
Since $1001\equiv 0$ modulo each of $7,11,13$, we get

$$\begin{array}{rl}10^3& \equiv -1(\mathrm{mod}7),(\mathrm{mod}11)\text{ and}(\mathrm{mod}13),\end{array}$$

so the 3-digit blocks alternate in sign, just like the $11$ test but with blocks instead of digits. For $12345$ the blocks from the right are $345$ and $12$;

$$\begin{array}{rl}345-12& =333.\end{array}$$

Now reduce $333$ by each prime: $333=7(47)+4$, so $12345\equiv 4(\mathrm{mod}7)$; $333=11(30)+3$, so $12345\equiv 3(\mathrm{mod}11)$; $333=13(25)+8$, so $12345\equiv 8(\mathrm{mod}13)$. Therefore $12345$ is divisible by none of $7$, $11$ or $13$ — and notice how the mod $7$ and mod $13$ remainders here are the actual remainders, consistent with (and more informative than) the truncation tests we ran on $12345$ earlier. For a satisfying yes-instance, take $999999$: its blocks give $999-999=0$, so $999999$ is divisible by $7$, $11$ and $13$ all at once.

So when you're handed an unfamiliar divisor on an exam, the decision goes:

• $n=2^a{5}^b$: look at the last $\max (a,b)$ digits.
• $n\in \{3,9,11\}$ (or you want a remainder cheaply): digit sums and alternating sums.
• $n$ composite: factorise into coprime prime powers and test each piece.
• $n$ some other prime: find a multiple of $n$ near a multiple of $10$ for a quick yes/no truncation test, or a power $10^k\equiv \pm 1(\mathrm{mod}n)$ if you also want remainders.

Table of Divisibility Tests

The lecture's full table, for quick revision:

Tests for primes (or prime powers) beyond $13$ are built exactly as in the previous section: seek small multiples of the prime that are $1$ more or $1$ less than a multiple of $10$, or a small power of $10$ that is $\pm 1$ mod the prime.