logo

3の倍数判定法と9の倍数判定法の証明 📂整数論

3の倍数判定法と9の倍数判定法の証明

定理

各桁の数字を全部足して 33 の倍数なら 33 の倍数で、99 の倍数なら 99 の倍数だ。

説明

例として

  • 81428142 は 8142=3⋅27148142=3 \cdot 2714 で 33 の倍数で、実際に 8+1+4+2=158+1+4+2=15 は 33 の倍数だ。
  • 19451251945125 は 1945125=9⋅2161251945125=9 \cdot 216125 で 99 の倍数で、実際に 1+9+4+5+1+2+5=271+9+4+5+1+2+5=27 は 99 の倍数だ。

倍数判定法は現代においてはあまり意味がなくなったが、依然として興味深いツールである。2,4,5,82,4,5,8 の倍数は判定がとても簡単だが、3,7,9,113, 7, 9, 11 などの数に対しては別の証明が必要だ。幸いにも7を除いては、証明も理解も簡単な方だ。

証明

戦略：証明の肝は、10のべき乗を1と99..99に分けて各桁の数字のみを考えることだ。この投稿では、証明時の便宜のために以下のような記法を使用することにする。

[anan−1…a1a0]=an⋅10n+an−1⋅10n−1+…+a1⋅101+a0⋅100 [a_{n} a_{n-1} … a_{1} a_{0}]= a_{n} \cdot 10^{n} + a_{n-1} \cdot 10^{n-1} +…+ a_{1} \cdot 10^{1} + a_{0} \cdot 10^{0} 例えば、57145714 は以下のように表すことができる。 [5714]=5000+700+10+4=5⋅103+7⋅102+1⋅101+4⋅100 [5714]=5000+700+10+4=5\cdot 10^{3} +7\cdot 10^{2} +1\cdot 10^{1} +4\cdot 10^{0} 証明が分からなければ、実際の例を見ながら考えてみるのが良い。

[anan−1…a1a0]=an⋅10n+an−1⋅10n−1+…+a1⋅101+a0⋅100=an⋅(10n−1)+an−1⋅(10n−1−1)+⋯+a1⋅(101−1)+a0+(an+an−1+…+a1)=∑k=1nak(10k−1)+∑k=0nak \begin{align*} & [a_{n} a_{n-1} … a_{1} a_{0}] \\ =& a_{n} \cdot 10^{n} + a_{n-1} \cdot 10^{n-1} +…+ a_{1} \cdot 10^{1} + a_{0} \cdot 10^{0} \\ =& a_{n} \cdot \left( 10^{n} -1 \right) + a_{n-1} \cdot \left( 10^{n-1} -1 \right) + \cdots + a_{1} \cdot \left( 10^{1} -1 \right) \\ & + a_{0} +\left( a_{n} + a_{n-1} +…+ a_{1} \right) \\ =& \sum_{k=1}^{n} a_{k} \left( 10^{k} - 1 \right) + \sum_{k=0}^{n} a_{k} \end{align*}

ここで 10n−1=[99…99]10^{n} -1=[99…99] は 33 と 99 の倍数である（例えば、103−1=99910^{3} -1=999）。だから、∑k=0nak\displaystyle \sum_{k=0}^{n} a_{k} が3の倍数なら、[anan−1…a1a0][a_{n} a_{n-1} … a_{1} a_{0}] も3の倍数だ。同様に、∑k=0nak\displaystyle \sum_{k=0}^{n} a_{k} が9の倍数なら、[anan−1…a1a0][a_{n} a_{n-1} … a_{1} a_{0}] も9の倍数だ。

■