# Solution

Prove each of the following for a given positive integer $n$:

1. $5 \mid n$ if and only if the last digit of $n$ is a $0$ or $5$
2. $9 \mid n$ if and only if the sum of the digits of $n$ is divisible by $9$
3. $3 \mid n$ if and only if the sum of the digits of $n$ is divisible by $3$

Suppose $n$ has digits $d_n d_{n-1} \cdots d_2 d_1 d_0$.

1. If we wish to show that $5 \mid n$ if and only if the last digit of $n$ is a $0$ or $5$:

$$\begin{array}{rcl} n &=& 10^n d_n + 10^{n-1} d_{n-1} + \cdots + 10^2 d_2 + 10 d_1 + d_0\\\\ &=& 10(10^{n-1} d_n + 10^{n-2} d_{n-1} + \cdots + 10 d_2 + d_1) + d_0 \end{array}$$

Looking at the first term, it is clear that $5$ divides $10(10^{n-1} d_n + 10^{n-2} d_{n-1} + \cdots + 10 d_2 + d_1)$ since $5 \mid 10$. Consequently, $5 \mid n$ if and only if $5$ divides the last term (i.e., $5 \mid d_0$).

Since a digit (like $d_0$) can only take on the integer values from $0$ to $9$, that leaves only two possibilities. $5 \mid n$ if and only if $d_0$ (the last digit) is a $0$ or a $5$, which is what we hoped to show.

2. If we wish to show $9 \mid n$ if and only if the sum of the digits of $n$ is divisible by $9$, we again start with

$$n = 10^n d_n + 10^{n-1} d_{n-1} + \cdots + 10^2 d_2 + 10 d_1 + d_0$$

The sum of the digits of $n$ is $(d_n + d_{n-1} + \cdots d_2 + d_1 + d_0)$, so let us separate out this piece, and see what is left:

$$n = (\underbrace{999\cdots9}_{n \textrm{ nines}} d_n + \underbrace{99\cdots9}_{n-1 \textrm{ nines}} d_{n-1} + \cdots + 99 d_2 + 9 d_1) + (d_n + d_{n-1} + \cdots d_2 + d_1 + d_0)$$

Clearly, $9$ divides the first expression in parentheses -- so if it is to divide the entire expression (and hence $n$), it must also divide the second expression in parentheses, $(d_n + d_{n-1} + \cdots d_2 + d_1 + d_0)$. The reverse holds as well, if $9$ divides the second expression, it will divide the sum of the two expressions, being a common factor. Consequently, $9 \mid n$ if and only if the sum of the digits of $n$ is divisible by $9$, which is what we hoped to show.

3. This argument is almost identical to the one used in part (b), except that we pull out a factor of $3$...