# Divisibility by 3

A common rule for checking whether an integer is divisible by `3`

is to consider
the sum of its digits.

For example, `12345`

is divisible by `3`

because `1 + 2 + 3 + 4 + 5 = 15`

,
and `15`

is divisible by `3`

.

Similarly, `123456`

is divisible by `3`

and `1234567`

is not.

Above, we are saying if the sum of an integer’s digits is divisible
by `3`

, then the integer is divisible by `3`

.

What about the reverse implication, i.e. if an integer is divisible by `3`

,
then the sum of its digits is divisible by `3`

?

`3 x 12345 = 37035`

is divisible by 3 thus the sum of its digits must also be
divisible by `3`

. Checking this, we have `3 + 7 + 0 + 3 + 5 = 18`

which is
indeed divisible by `3`

.

Similary, `3 x 234829042390482 = 704487127171446`

is divisible by `3`

and
`7 + 0 + 4 + 4 + 8 + 7 + 1 + 2 + 7 + 1 + 7 + 1 + 4 + 4 + 6 = 63`

is divisible
by 3.

If both implications are true, this means the set of integers that are divisble
by `3`

is **exactly the same set of integers** whose sum of digits is divisible
by `3`

.

In other words,
it is impossible to find an integer that is divisible by `3`

whose sum of
its digits is not divisible by `3`

or vice versa.

To “approximately” check if this is true in Python,

```
def get_sum_of_digits(n):
return sum(int(i) for i in list(str(n)))
i = 0
while True:
sum_of_digits = get_sum_of_digits(i)
if ((i % 3 == 0 and sum_of_digits % 3 != 0) or
(i % 3 != 0 and sum_of_digits % 3 == 0)):
print(f'The double implication (equivalence) is false for {i}!')
break
else:
print(i)
i += 1
```

Which for me ran until `i = 6624839`

before I quit the script.

Unfortunately, whilst we can check our double implication is true for an arbitrarily large number of integers, we cannot check it in its full form.

As the set of integers is infinite, it would take us an infinity to check using the method above!

However, we can achieve the above using mathematical logic:

$Let\;n\;\in\;\mathbb{N}.$

$We\;define\;\varphi(n)\;as\;the\; sum\;of\;the\;digits\;of\;n\;and\;d(n)\;as\;the\;number\;of\;digits$

$of\;n. \; For\;example,\;\varphi(123)=6\;and\;d(n)=3$

$Show \; that:$

\[\forall n \in \mathbb{N},\;n\mod p = 0 \iff \varphi(n) \mod p = 0 \; (*)\]$where \; p=3$

We proceed by induction.

We note

\[\mathcal{P}(n): \;n\mod 3 = 0 \iff \varphi(n) \mod 3 = 0\]and use the notation $n=a_{1}\cdots a_{k}$

E.g. for $n=231$, $a_1=2$, $a_2=3$, $a_3=1$.

Let’s verify $\mathcal{P}(0)$,

\[0 \mod 3 = 0 \iff \varphi(0) \mod 3 = 0\]which is true as $\varphi(0)=0$.

Let $n \in \mathbb{N}$.

Suppose $\mathcal{P}(k)$, $k \in [0..n]$.

We want to show $\mathcal{P}(n+1)$,

\[\mathcal{P}(n+1): n+1\mod 3 = 0 \iff \varphi(n+1) \mod 3 = 0\]If $n+1 \lt 10$, then $\varphi(n+1)=n+1 \implies \mathcal{P}(n+1)$.

If $n+1 \geq 10$, we have the following cases:

- $n+1=a_1\cdots a_{k-1}9, \; k \geq 2$; it follows that $(n+1)-9 = a_1\cdots a_{k-1}0$.

Thus

\[\begin{aligned} n+1\mod 3 = 0 &\iff (n+1) -9\mod 3 = 0\\ &\iff \varphi((n+1) -9)\mod 3 = 0\\ &\iff \varphi((n+1) -9)+9\mod 3 = 0\\ &\iff \varphi(n+1)\mod 3 = 0 \end{aligned}\]- $n+1=a_1\cdots a_{k}, \; a_k \neq 9$

Suppose $d(n+1)=d((n+1)-9)$. Then

\[a_k \in [0..8] \implies a_{k-1} \gt 0\]If we write $(n+1)-9=b_{1}\cdots b_{k}$, we have $b_{k-1}=a_{k-1}-1$, $b_{k}=a_{k}+1$ and $a_i=b_i, \; i \in [1..k-2]$

Therefore

\[\begin{aligned} \varphi(n+1)&=\sum_{i=1}^{k}a_i\\ &=\sum_{i=1}^{k-2}b_i+b_{k-1}+1+b_{k}-1\\ &=\sum_{i=1}^{k}b_i\\ &=\varphi((n+1)-9) \end{aligned}\]Thus

\[\begin{aligned} \varphi(n+1) \mod 3 = 0 &\iff \varphi((n+1)-9) \mod 3 = 0\\ &\iff (n+1) - 9 \mod 3 = 0\\ &\iff n+1 \mod 3 =0 \end{aligned}\]Otherwise, $d(n+1)\neq d((n+1)-9) \implies d(n+1) = d((n+1)-9) +1$

Thus

\[n+1=a_1\cdots a_k; \; a_1=1,a_2=\ldots =a_{k-1}=0,a_k \in [0..8] \\\]and

\[(n+1)-9=b_1\cdots b_{k-1}; \; b_1=\ldots =b_{k-2}=9, b_{k-1}=a_{k}+1\]so

\[\begin{aligned} \varphi(n+1)-\varphi((n+1)-9)&=\sum_{i=1}^{k}a_i - \sum_{i=1}^{k-1}b_i\\ &=1+a_{k}-9-\ldots -9 - a_{k}-1\\ &=9q, \; q\in\mathbb{Z} \end{aligned}\]which gives

\[\begin{aligned} \varphi(n+1)\mod 3=0 &\iff \varphi((n+1)-9) \mod 3 =0\\ &\iff (n+1)-9 \mod 3 =0 \\ &\iff n+1 \mod 3 =0\\ \end{aligned}\]Conclusion:

$\mathcal{P}(0)$ true, and for all $n \in \mathbb{N}$,

\[\mathcal{P}(k), \; k \in [0..n] \implies \mathcal{P}(n+1)\]thus by induction, $\mathcal{P}(n)$, $n \in \mathbb{N}$, QED.

We have showed $(*)$ is true for $p=3$.

Is $(*)$ true for all $p$?

No, for $p=2$ and $n=10$, we have $10 \mod 2 =0$ but $\varphi(10) \mod 2 =1$.

Are there any other $p$ for which $(*)$ is true?

How would changing the base from ten affect any results?