Divisibility Tricks

Let $n$ be an integer between $0$ and $9$ inclusive. It is obvious that:

$n$ is even if and only if $n$ is one of the numbers $0, 2, 4, 6, 8$
$n$ is a multiple of $3$ if and only if $n$ is one of the numbers $0, 3, 6, 9$ .
$n$ is a multiple of $5$ if and only if $n$ is one of the numbers $0, 5$ .

Let $m$ be number between $1$ and $9$ inclusive. Define the two-digit number

$x(m,n) := 10m + n.$

For example, $x(6, 7) = 10 \times 6 + 7 = 67$ .

Problem 1. Show that $x(m, n)$ is even if and only if $n$ is even (i.e. $n$ is one of $0, 2, 4, 6, 8$ ).

(Click for Solution)

Solution. Write $x(m,n) = 10m + n$ so that

$n = x(m,n) - 10m.$

$(\Rightarrow)$ If $x(m,n)$ is even, then there exists an integer $k$ such that $x(m,n) = 2k$ . Hence,

$\begin{aligned} n &= x(m,n) - 10m \\ &= 2k - 10m \\ &= 2(k-5m). \end{aligned}$

Since $k - 5m$ is still an integer, $n$ must be even.

$(\Leftarrow)$ If $n$ is even, then there exists an integer $\ell$ such that $n = 2 \ell$ . Hence,

$\begin{aligned} x(m,n) &= 10m + n \\ &= 10m + 2\ell \\ &= 2(5m + \ell). \end{aligned}$

Since $5m + \ell$ is still an integer, $x(m,n)$ must be even.

Remark 1. The same proof can be modified to show that $x(m, n)$ is a multiple of $5$ if and only if $n$ is either $0$ or $5$ . Furthermore, $x(m, n)$ is a multiple of $10$ if and only if $n = 0$ . These results work for numbers regardless of the number of digits, for example:

$123\, 456$ is even,
$123\, 455$ is a multiple of $5$ ,
$123\, 450$ is a multiple of $10$ .

We remark that the one-digit multiples of $3$ are

$\begin{aligned} 3 &= 3 \times 1,\\ 6 &= 3 \times 2,\\ 9 &= 3 \times 3. \end{aligned}$

Problem 2. Show that $x(m, n)$ is a multiple of $3$ if and only if $m+n$ is a multiple of $3$ .

(Click for Solution)

Solution. By definition,

$x(m,n) = 10m + n = 9m + (m+n),$

so that $m+n = x(m,n) - 9m$ .

$(\Rightarrow)$ If $x(m,n)$ is a multiple of $3$ , then there exists an integer $k$ such that $x(m,n) = 3k$ . Hence,

$\begin{aligned} m+n &= x(m,n) - 9m \\ &= 3k - 9m \\ &= 3(k-3m). \end{aligned}$

Since $k - 3m$ is still an integer, $m+n$ must be a multiple of $3$ .

$(\Leftarrow)$ If $m+n$ is a multiple of $3$ , then there exists an integer $\ell$ such that $m+n = 3 \ell$ . Hence,

$\begin{aligned} x(m,n) &= 9m + (m+n) \\ &= 9m + 3\ell \\ &= 3(3m + \ell). \end{aligned}$

Since $3m + \ell$ is still an integer, $x(m,n)$ must be a multiple of $3$ .

Example 1. $57$ is a multiple of $3$ , because

$57 \to 5+7 = 12 \to 1+2 = 3.$

This result works for numbers regardless of the number of digits: since

$12\, 357 \to 1+2+3+5+7 = 18 \to 1+8 = 9,$

$12\, 357$ is a multiple of $3$ .

Remark 2. The same proof can be modified to show that $x(m, n)$ is a multiple of $9$ if and only if $m+n$ is a multiple of $9$ . Furthermore, we can use more advanced techniques to reduce all calculations to the set of one-digit numbers $\{1,2,\dots, 9\}$ .

Now let $n_1, n_2, n_3$ be numbers in $0,1,2,\dots, 9$ , and $n_1 > 0$ . Define the three-digit number

$y(n_1,n_2,n_3) := 100n_1 + 10n_2 + n_3.$

For example

$y(4,2,0) = 100 \times 4 + 10 \times 2 + 0 = 420.$

We remark that the first five multiples of $4$ are

$\begin{aligned} 4 &= 4 \times 1,\\ 8 &= 4 \times 2,\\ 12 &= 4 \times 3, \\ 16 &= 4 \times 4, \\ 20 &= 4 \times 5. \end{aligned}$

Furthermore, $0 = 4 \times 0$ is a multiple of $4$ .

Problem 3. Show that:

$x(n_2,n_3)$ is a multiple of $4$ if and only if there exists a positive integer $k$ such that $x(n_2 - 2k, n_3)$ is a multiple of $4$ ,
$y(n_1, n_2, n_3)$ is a multiple of $4$ if and only if $x(n_2,n_3)$ is a multiple of $4$ .