Example
An integer \(n\) is divisible by \(3\) if and only if the sum of its digits is divisible by \(3\)

Proof

Let \(n \in \mathbb{Z}\). Then we can write \(3\) in base \(10\) as

$$ \begin{align*} n = 10^{k} \cdot d_k + 10^{k-1} \cdot d_{k-1} + \cdots + 10^{0} \cdot d_0. \end{align*} $$

and let be the sum of digits in \(n\) so

$$ \begin{align*} d = d_k + d_{k-1} + \cdots + d_0 \end{align*} $$

We are given that \(3 \mid d\). Therefore,

$$ \begin{align*} d &= 3m \quad \text{ for some } m \in \mathbb{Z} \end{align*} $$

Consider now \(n - d\). Then

$$ \begin{align*} n - d &= (10^{k} \cdot d_k + 10^{k-1} \cdot d_{k-1} + \cdots + 10^{0} \cdot d_0) - (d_k + d_{k-1} + \cdots + d_0) \\ &= d_k(10^k - 1) + d_{k-1}(10^{k-1} - 1) + \cdots d_1(10 - 1) + (d_0 - d_0) \\ &= d_k(10^k - 1) + d_{k-1}(10^{k-1} - 1) + \cdots (10 - 1)d_1 \end{align*} $$

But now observe that \(10^m - 1\) is divisible by \(3\) for any \(m \in \mathbb{N}\).

Why? By Induction on \(m \in \mathbb{n}\). The base case is \(10^1 - 1\) is divisible by \(3\). For the inductive case, suppose that \(10^m-1\) is divisible by \(3\). $$ \begin{align*} 10^{m+1} - 1 &= 10 \cdot 10^{m} - 1 \\ &= 10(10^{m} - 1) + 9 \end{align*} $$ Observe now that the first term is divisible by \(3\) by the inductive hypothesis and the second term is \(9\) so it's divisible by \(3\). Therefore, \(10^m - 1\) is divisible by \(3. \ \blacksquare\)

So now we have

$$ \begin{align*} n - d &= d_k(10^k - 1) + d_{k-1}(10^{k-1} - 1) + \cdots (10 - 1)d_1 \end{align*} $$

where each term on the right is divisible by \(3\) so the entire sum is divisible by \(3\) and so we can re-write this as

$$ \begin{align*} n - d &= 3 \cdot t \quad \text{ for some } t \in \mathbb{Z} \end{align*} $$

But since \(3 \mid\), then we must have that \(3 \mid n\) as we wanted to show. \(\ \blacksquare\)


References

  • Math310 Class Notes