1.18: Divisibility Tests for 2, 3, 5, 9, 11

Recall from Definition 1.6.1 that the decimal representation of the positive integer \(a\) is given by \[\label{decimal} a=a_{n-1}a_{n-2}\dotsm a_1a_0\] when \[a=a_{n-1}10^{n-1}+a_{n-2}10^{n-2}+\dotsb+a_110+a_0\nonumber \] and \(0\le a_i\le 9\) for \(i=0,1,\dotsc,n-1\).

Theorem \(\PageIndex{1}\)

Let the decimal representation of \(a\) be given by \(a=a_{n-1}a_{n-2}\dotsm a_1a_0\). Then

1. \(a\bmod 2=a_0\bmod 2\),
2. \(a\bmod 5=a_0\bmod 5\),
3. \(a\bmod 3=\left(a_{n-1}+\dotsb+a_0\right)\bmod 3\),
4. \(a\bmod 9=\left(a_{n-1}+\dotsb+a_0\right)\bmod 9\),
5. \(a\bmod 11=\left(a_0-a_1+a_2-a_3+\dotsb\right)\bmod 11\).

Before proving this theorem, let’s give some examples. \[\begin{aligned} 1457\bmod 2 &=7\bmod 2=1; \\ 1457\bmod 5 &=7\bmod 5=2;\end{aligned}\] \[\begin{split} 1457\bmod 3 =(1+4+5+7)\bmod 3 &=17\bmod 3 \\= (1+7)\bmod 3 &=8\bmod 3=2; \end{split}\] \[\begin{split} 1457\bmod 9 &=(1+4+5+7)\bmod 9 \\ &=17\bmod 9 \\&=(1+7)\bmod 9\\ &=8\bmod 9 \\ &=8; \end{split}\] \[\begin{split} 1457 \bmod 11 &=(7-5+4-1)\bmod 11 \\ &=5\bmod 11 \\ &=5. \end{split}\]

Proof of Theorem \(\PageIndex{1}\)

Proof

Consider the polynomial \[f(x)=a_{n-1}x^{n-1}+\dotsb+a_1x+a_0.\nonumber \] Note that \(10\equiv 0\pmod 2\). So by Theorem 1.17.3 (4) \[a_{n-1}10^{n-1}+\dotsb+a_110+a_0\equiv a_{n-1}0^{n-1}+\dotsb+a_10+a_0\pmod 2.\nonumber \] That is, \[a\equiv a_0\pmod 2.\nonumber \] This, together with Theorem 1.17.1, proves part (a). Since \(10\equiv 0\pmod 5\), the proof of part (b) is similar.

Note that \(10\equiv 1\pmod 3\), so applying Theorem 1.17.3 (4) again, we have \[a_{n-1}10^{n-1}+\dotsb+a_110+a_0\equiv a_{n-1}1^{n-1}+\dotsb+a_11+a_0\pmod 3.\nonumber \] That is, \[a\equiv a_{n-1}+\dotsb+a_1+a_0\pmod 3.\nonumber \] This, using Theorem 1.17.1, proves part (c). Since \(10\equiv 1\pmod 9\), the proof of part (d) is similar.

Now \(10\equiv-1\pmod{11}\) so \[a_{n-1}10^{n-1}+\dotsb+a_110+a_0\equiv a_{n-1}(-1)^{n-1}+\dotsb+a_1(-1)+a_0\pmod{11}.\nonumber \] That is, \[a\equiv a_0-a_1+a_2-\dotsb\pmod{11}\nonumber \] and by Theorem 1.17.1 we are done.

Remark \(\PageIndex{1}\)

Note that \[m\mid a\Leftrightarrow a\bmod m=0,\nonumber \] so from Theorem \(\PageIndex{1}\) we obtain immediately the following corollary.

Corollary \(\PageIndex{1}\)

Let \(a\) be given by expression \(\eqref{decimal}\). Then

1. \(2\mid a\Leftrightarrow a_0=0,2,4,6\) or \(8\)
2. \(5\mid a\Leftrightarrow a_0=0\) or \(5\)
3. \(3\mid a\Leftrightarrow 3\mid (a_0+a_1+\dotsb+a_{n-1})\)
4. \(9\mid a\Leftrightarrow 9\mid (a_0+a_1+\dotsb+a_{n-1})\)
5. \(11\mid a\Leftrightarrow 11\mid (a_0-a_1+a_2-a_3+\dotsb)\).

Note that in applying (c), (d) and (e) we can use the fact that \[(a+m) \bmod m = a\nonumber \] to “cast out” \(3\)’s (for (c)) and \(9\)’s (for (d)). Here’s an example of “casting out \(9\)’s:” \[\begin{split} 1487\bmod 9 &=(1+4+8+7) \bmod 9 \\ &=(9+4+7)\bmod 9 \\ &=(4+7)\bmod 9 \\ &=(2+9) \bmod 9 \\ &=2\bmod 9=2. \end{split}\] So \(1487\bmod 9=2\).

\[\boxed{\begin{array}{c}\text{Note that if }0\leq r<m\text{ then } \\ r\bmod m=4.\end{array}}\nonumber\]

Exercises

Exercise \(\PageIndex{1}\)

Let \(a=18726132117057\). Find \(a \bmod m\) for \(m=2,3,5,9\) and \(11\).

Exercise \(\PageIndex{2}\)

Use the divisibility test presented in this chapter to determine the next year after this one that will be divisible by 11.

Exercise \(\PageIndex{3}\)

Let \(a=a_n\dotsm a_1a_0\) be the decimal representation of \(a\). Then prove

1. \(a\bmod 10=a_0\).
2. \(a\bmod 100=a_1a_0\).
3. \(a\bmod 1000=a_2a_1a_0\).

Exercise \(\PageIndex{4}\)

Prove that if \(b\) is a positive square, i.e., \(b=a^2\), \(a>0\), then the least significant digit of \(b\) is one of \(0\), \(1\), \(4\), \(5\), \(6\), \(9\).

(Hint: \(b\bmod 10\) is the least significant digit of \(b\). Write \(a=a_{n-1}\dotsm a_0\). Then \(a\equiv a_0\pmod{10}\) so \(a^2\equiv a_0^2\pmod{10}\). For each digit \(a_0\in\{0,1,2,\dotsc,9\}\) find \(a_0^2\bmod 10\). Use Theorem 1.17.4, among other results.)

Exercise \(\PageIndex{5}\)

Write down, with proof, a statement like that in Exercise \(\PageIndex{4}\) that tests whether \(b\) is a positive square by looking at the last two digits of its decimal representation.

Exercise \(\PageIndex{6}\)

Are any of the following numbers squares? Explain, without using a device to take a square root. \[10, \quad 11, \quad 16, \quad 19, \quad 24, \quad 25, \quad 272,\quad 2983,\quad 11007,\quad 1120378\nonumber \]