logo

7と13の倍数判定法の証明 📂整数論

7と13の倍数判定法の証明

ビルドアップ

このポストでは、基数に関する便宜のために、次のような表記を使っている。 [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 \begin{align*} [5714] =& 5000+700+10+4 \\ =& 5\cdot 10^{3} +7\cdot 10^{2} +1\cdot 10^{1} +4\cdot 10^{0} \end{align*}

定理

anan−1an−2−an−3an−4an−5+…+a5a4a3−a2a1a0 a_{n} a_{n-1} a_{n-2} - a_{n-3} a_{n-4} a_{n-5} +…+ a_{5} a_{4} a_{3} - a_{2} a_{1} a_{0} これが77の倍数なら、[anan−1…a1a0][a_{n} a_{n-1} … a_{1} a_{0}]も77の倍数で、 anan−1an−2−an−3an−4an−5+…+a5a4a3−a2a1a0 a_{n} a_{n-1} a_{n-2} - a_{n-3} a_{n-4} a_{n-5} +…+ a_{5} a_{4} a_{3} - a_{2} a_{1} a_{0} これが1313の倍数なら、[anan−1…a1a0][a_{n} a_{n-1} … a_{1} a_{0}]も1313の倍数だ。

説明

これがどういう意味かというと、各桁の数を3つずつグループにして、交代で足したり引いたりした数が77の倍数なら、元の数も7の倍数だってことだ。例を見て理解してみよう。

例えば、745444745444を見れば、判定法によって 745−444=7⋅301 745-444=7 \cdot 301 で7の倍数だけど、実際に745444745444は745444=7⋅106492745444=7 \cdot 106492で77の倍数だ。もっと大きな数の1179454511794545を見ても、上の判定法はまだしっかりと当てはまってて、 −11+794−545=238=7⋅34 -11+794-545 = 238 = 7 \cdot 34 は77の倍数で、実際には1179454511794545も11794545=7⋅168493511794545=7 \cdot 1684935で77の倍数だ。

この定理は1313の場合にも成立して、実は1111の場合にも成立する。その理由は77の倍数判定法と1111の倍数判定法と1313の倍数判定法が全部同じ証明から出てくるからだ。数字を変えただけで完全に同じ証明なので、1111の場合と1313の場合は省略するよ。

証明

ストラテジー：証明自体はとても基本的なテクニックのみを使っているが、本質的に長くてアイデアも必要だから簡単ではない。キーとなるアイデアは、10011001と999999999999が77の倍数であるという事実を使うことだ。 103+1=1000+1=1001=7⋅143(103+1)(103−1)=106−1=1000000−1=999999=7⋅142857 10^{3} +1=1000+1=1001=7\cdot 143 \\ \left( 10^{3} +1 \right) \left( 10^{3} -1 \right) = 10^{6} -1=1000000-1=999999=7\cdot 142857

[anan−1…a1a0]=[anan−1an−2]10n−2+[an−3an−4an−5]10n−5+…+[a5a4a3]103+[a2a1a0]=([anan−1an−2]103+[an−3an−4an−5])10n−5+…+([a5a4a3]103+[a2a1a0]) \begin{align*} & [a_{n} a_{n-1} … a_{1} a_{0}] \\ =& [a_{n} a_{n-1} a_{n-2} ]10^{n-2} +[a_{n-3} a_{n-4} a_{n-5}]10^{n-5} +…+[a_{5} a_{4} a_{3}]10^{3} +[a_{2} a_{1} a_{0}] \\ =& ([a_{n} a_{n-1} a_{n-2}]10^{3} +[a_{n-3} a_{n-4} a_{n-5}]) 10^{n-5} +…+([a_{5} a_{4} a_{3}]10^{3} +[a_{2} a_{1} a_{0}]) \end{align*}

括弧で囲み部分だけを見れば、

([anan−1an−2]103+[an−3an−4an−5])=[anan−1an−2]103+([anan−1an−2]−[anan−1an−2])+[an−3an−4an−5]=([anan−1an−2]103+[anan−1an−2])−([anan−1an−2]−[an−3an−4an−5])=[anan−1an−2]1001−([anan−1an−2]−[an−3an−4an−5])=[anan−1an−2]7⋅143−([anan−1an−2]−[an−3an−4an−5]) \begin{align*} & ([a_{n} a_{n-1} a_{n-2}]10^{3} +[a_{n-3} a_{n-4} a_{n-5}]) \\ &= {[a_{n} a_{n-1} a_{n-2}]10^{3} +([a_{n} a_{n-1} a_{n-2}]-[a_{n} a_{n-1} a_{n-2}])+[a_{n-3} a_{n-4} a_{n-5}]} \\ &= {([a_{n} a_{n-1} a_{n-2}]10^{3} +[a_{n} a_{n-1} a_{n-2}])- ([a_{n} a_{n-1} a_{n-2}]-[a_{n-3} a_{n-4} a_{n-5}])} \\ &= {[a_{n} a_{n-1} a_{n-2}]1001-([a_{n} a_{n-1} a_{n-2}]-[a_{n-3} a_{n-4} a_{n-5}])} \\ &= [a_{n} a_{n-1} a_{n-2}]7\cdot 143-([a_{n} a_{n-1} a_{n-2}]-[a_{n-3} a_{n-4} a_{n-5}]) \end{align*}

つまり、 ([anan−1an−2]−[an−3an−4an−5]) ([a_{n} a_{n-1} a_{n-2}]-[a_{n-3} a_{n-4} a_{n-5}]) これが77の倍数なら、 [anan−1an−2an−3an−4an−5] [a_{n} a_{n-1} a_{n-2} a_{n-3} a_{n-4} a_{n-5}] も77の倍数だ。 さて、一般化してみよう。

([anan−1an−2]103+[an−3an−4an−5])10n−5=[anan−1an−2]7⋅143⋅10n−5−([anan−1an−2]−[an−3an−4an−5])10n−5 \begin{align*} & ([a_{n} a_{n-1} a_{n-2}]10^{3} +[a_{n-3} a_{n-4} a_{n-5}]) 10^{n-5} \\ &= [a_{n} a_{n-1} a_{n-2}]7\cdot 143\cdot 10^{n-5} -([a_{n} a_{n-1} a_{n-2}]-[a_{n-3} a_{n-4} a_{n-5}]) 10^{n-5} \end{align*}

ここで、[anan−1an−2]7⋅143⋅10n−5[a_{n} a_{n-1} a_{n-2}]7\cdot 143\cdot 10^{n-5}のような項を全部77でグループ化して、ccとして表せば、

[anan−1…a1a0]=7c+([anan−1an−2]−[an−3an−4an−5])10n−5+…+([a5a4a3]−[a2a1a0]) \begin{align*} & [a_{n} a_{n-1} … a_{1} a_{0}] \\ =& 7c+([a_{n} a_{n-1} a_{n-2}]-[a_{n-3} a_{n-4} a_{n-5}]) 10^{n-5} +…+([a_{5} a_{4} a_{3}]- [a_{2} a_{1} a_{0}]) \end{align*}

ccが何であれ、7c7cは確実に77の倍数なので、ここで後半部分が77の倍数なら証明は完了する。そして、ここで999999999999の性質が使われる。

A106=A106−A+A=(106−1)A+A=999999A+A=7⋅142857A+A=7c+A \begin{align*} A 10^{6} &=A 10^{6} -A+A \\ &=( 10^{6} -1)A+A \\ &=999999A+A \\ &=7\cdot 142857A+A \\ &=7c+A \end{align*}

上の式が成り立つので、1010の累乗は、77で割り切れる定数項を出し、次数を66ずつ減らしていける。

[anan−1…a1a0]=7c+([anan−1an−2]−[an−3an−4an−5])10n−5+…+([a5a4a3]−[a2a1a0]) \begin{align*} & [a_{n} a_{n-1} … a_{1} a_{0}] \\ =& 7c+([a_{n} a_{n-1} a_{n-2}]-[a_{n-3} a_{n-4} a_{n-5}]) 10^{n-5} +…+([a_{5} a_{4} a_{3}]- [a_{2} a_{1} a_{0}]) \end{align*}

上の式では、n−5,n−11,…,0n-5, n-11, … ,0はすべて66の倍数なので、

[anan−1…a1a0]=7c+([anan−1an−2]−[an−3an−4an−5])+…+([a5a4a3]−[a2a1a0]) \begin{align*} & [a_{n} a_{n-1} … a_{1} a_{0}] \\ =& 7c+([a_{n} a_{n-1} a_{n-2}]-[a_{n-3} a_{n-4} a_{n-5}])+…+([a_{5} a_{4} a_{3}]-[a_{2} a_{1} a_{0}]) \end{align*}

従って、

[anan−1an−2]−[an−3an−4an−5]+…+[a5a4a3]−[a2a1a0] [a_{n} a_{n-1} a_{n-2}]- [a_{n-3} a_{n-4} a_{n-5}]+…+[a_{5} a_{4} a_{3}]-[a_{2} a_{1} a_{0}]

これが77の倍数なら、[anan−1…a1a0][a_{n} a_{n-1} … a_{1} a_{0}]も77の倍数だ。

1001=7⋅143=7⋅11⋅131001 = 7 \cdot 143 = 7 \cdot 11 \cdot 13という点を考えると、1111であれ1313であれ、証明はもう終わっているも同然だ。

■