3の倍数の証明

Proof_of_multiples_of_3.md

定理

3の倍数の各桁の総和は、3の倍数である。

$$ \begin{align} 3n & = \sum_{k} 10^k a_k \Rightarrow \sum_{k} a_k = 3m \\ & \because \ n, m \in \mathbb{N} \ , \ a_k \in [0, 9] \end{align} $$

証明

3の剰余を $\equiv_3$ と記載する。

$$ \begin{align} 3n & = \sum_{k} 10^k a_k \\ & = \sum_{k} ((10^k-1) a_k + a_k) \\ & \equiv_3 \sum_{k} (0 \cdot a_k + a_k) \qquad (補題より) \\ & \equiv_3 \sum_{k} a_k \\ & \equiv_3 0 \end{align} $$

$$ \therefore \quad 3n = \sum_{k} 10^k a_k \Rightarrow \sum_{k} a_k = 3m $$

補題

$$ \begin{align} (10^k-1) & = (10^k - 1^k) \\ & = (10 - 1) \sum_{i} 10^{k-1-i} \cdot 1^i \\ & \equiv_3 0 \cdot \sum_{i} 10^{k-1-i} \cdot 1^i \\ & \equiv_3 0 \end{align} $$