A number theory problem by Lucas Tan

Let $x=a+10b+100c+1000d...$

The number concerned here would be $a+10b+100c... - (a+b+c...)=9b+99c+999d...$ , which is always divisible by 9, hence always divisible by 3.

Let $x = \sum_{all r} 10^r a_r$ , where $a_r, r \in \mathbb Z$ , $a_r \in [0, 9]$ and $r \in [0, \infty)$ .

$x - \sum a_r$

$= \sum 10^r a_r - \sum a_r$

$= \sum (10^r - 1)a_r$

Assume $10^n - 1$ is a multiple of $9$ .

$10^{n+1} - 1$

$= 10(10^n) - 1$

$= 10(10^n -1 + 1) -1$

$=90k + 9$ , where $k \in \mathbb Z$ $\Rightarrow 10^{n+1} -1$ is a multiple of $9$ .

$\therefore$ $10^n -1$ is a multiple of $9$ for all $n$ . (proven)

$\therefore$ $x - \sum a_r = \sum (10^r - 1)a_r$ is a multiple of $9$ for any positive integer $x$ . (proven)

Since the number is a multiple of $9$ , it must be a multiple of $3$ .

$$

For fun:

a. Let $x$ from the above solution be a multiple of $9$ $\Rightarrow x = 9m$ , where $m \in \mathbb Z$

Hence $9m - \sum a_r = 9k$

$\sum a_r = 9(m - k)$

$\therefore$ the digit sum is a multiple of $9$ .

$$

b. Consider $9n = 10a_1 + a_0$ , where $a_0, a_1 \in \mathbb Z^+$ . Assume $a_0 + a_1 = 9k, k \in \mathbb Z^+$

For $n + 1$ ,

$9n + 9$

$=10a_1 + a_0 + (10 - 1)$

$=10(a_1 +1) + (a_0 - 1)$

$\therefore (a_1 + 1) + (a_0 -1) = a_1 + a_0 = 9k$

To disprove $a_1 + a_0 \neq 9k$ , consider $n = 1$

$9(1) = 10(0) + 9$

$a_1 + a_0 = 0 + 9 = 9$

$\therefore a_1 + a_0 = 9k$ $\forall$ $9n = 10a_1 + a_0$ by induction.

From $9k = a_1 + a_0$ , let $a_1 = 10b_1 + b_0$

$\therefore 9k = 10(b_1) + (a_0 + b_0)$

$\Rightarrow a_0 + b_0 + b_1 = 9k'$ , where $k' \in \mathbb Z^+$

By induction, for all multiples of $9$ , the digit sum is a multiple of $9$ ( $\because b_1$ can be expressed as $10c_1 + c_0$ and so on).

$$

c. Recall that $10^n - 1$ is a multiple of $9$ $\forall$ $n$ .

Let $9k = \sum_{all r} 10^r a_r$ , where $a_r, r, k \in \mathbb Z$ , $a_r \in [0, 9]$ and $r \in [0, \infty)$ .

For any integer $\alpha$ ,

$\alpha (10^n)$ $= \alpha (10^n -1 +1)$

$= 9m + \alpha , m \in \mathbb Z$

$\equiv \alpha$ mod $9$

$\because 9k \equiv 0$ mod $9$ ,

$\sum 10^r a_r \equiv 0$ mod $9$

$\sum a_r \equiv 0$ mod $9$

$\Rightarrow \sum a_r = 9m'$ , where $m' \in \mathbb Z$

$\therefore$ the digit sum of a multiple of $9$ is a multiple of $9$ .

Let's say we have a two digit no. with digits a and b. 10a + b - ( a+b) = 9a-9b = 9(a-b) Note that we can always factor out 9. So 9 is definitely a factor. Since 9 is a factor, we can be sure that 3 is also a factor as 9= 3*3. So we can be sure that 3 is the smallest factor other than 1. Note that this method works for all numbers no matter the number of digits.

Never thought this also happens..ah nature has its own interesting patterns

The divisibility rule of 3 is that the sum of all its digits is divisible by 3. If you take the sum of a number's digits and subtract it again, you will end up with 0, which is divisible by 3.