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