Application: Divisibility criteria

In grade school, you probably learned the rule that an integer is divisible by $3$ if and only if the number of it's digits is divisible by $3$ . There is a similar criteria for divisibility by $9$ which sometimes goes by the name ``casting out nines''.

From the m-ary expansion of an integer, one can deduce other useful divisibility criteria. In this section, we outline a few of the better-known divisibility tests based on the decimal expansion of an integer, and defer the proofs of these tests to section 1.7 (although the reader is invited to prove as many of these tests as she/he can).

Let

$$a=a_k10^k+...a_1 10+a_0,$$

where $0\leq a_i\leq 9$ are the digits.

By 2

: $2\vert a$ if and only if $2\vert a_0$ .

By 3

: $3\vert a$ if and only if $3\vert(a_0+a_1+...+a_k)$ .

By 4

: $4\vert a$ if and only if $4\vert(a_0+a_1 10)$ .

By 5

: $5\vert a$ if and only if $5\vert a_0$ .

By 6

: $6\vert a$ if and only if $2\vert a$ and $3\vert a$ .

By 7

: $7\vert a$ if and only if

$$\begin{array}{cc} 7\vert(& a_0+10a_1+100a_2 + a_6 +10a_7 +10... ... & -a_3-10a_4-100a_5 - a_9-10a_{10}-100a_{11}-...). \end{array}$$

For example, $7\vert 100100$ .

For a proof of this criterion, see Example 1.7.6.

By 8

: $8\vert a$ if and only if $8\vert(a_0+10a_1+100a_2)$ .

For a proof of this criterion, see Example 1.7.6.

By 9

: $9\vert a$ if and only if $9\vert(a_0+a_1+...+a_k)$ .

For example, $9\vert 11115$ .

By 10

: $10\vert a$ if and only if $a_0=0$ .

By 11

: $11\vert a$ if and only if $11\vert(a_0+a_2+a_4+...-a_1-a_3-a_5...)$ .

For example, $11\vert 511115$ .

In fact, this divisibility rule is the basis for the ``ISBN code'' (an error-detecting code used internationally in labeling books) whch we shall study later.

By 12

: $12\vert a$ if and only if $3\vert a$ and $4\vert a$ .

By 13

: $13\vert a$ if and only if

$$\begin{array}{cc} 13\vert(& a_0+10a_1+100a_2 + a_6 +10a_7 +1... ... & -a_3-10a_4-100a_5 - a_9-10a_{10}-100a_{11}-...). \end{array}$$

For example, $13\vert 123123$ .