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

Recall from Definition 4.2 that the decimal representation of the positive integer \(a\) is given by \[\label{eq:1} 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 (1), 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\).

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 15.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 15.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 15.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 15.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 15.1 we are done.

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 \\ &=8\bmod 3=2 \end{split}\] \[\begin{split} 1457\bmod 9 &=(1+4+5+7)\bmod 9 \\ &=17\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}\]

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 (1), p. . 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\).

Note \(\PageIndex{1}\)

Note that if \(0\leq r<m\) then

\[r\bmod m=r.\nonumber\]

Exercise \(\PageIndex{1}\)

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

Exercise \(\PageIndex{2}\)

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{3}\)

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 15.4, among other results.

Exercise \(\PageIndex{4}\)

Are any of the following numbers squares? Explain. \[10, \quad 11, \quad 16, \quad 19, \quad 24, \quad 25, \quad 272,\quad 2983,\quad 11007,\quad 1120378\nonumber\]