7と13の倍数判定法の証明
ビルドアップ
このポストでは、基数に関する便宜のために、次のような表記を使っている。 $$ [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} $$ 例として、$5714$は以下のように表せる。 $$ \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*} $$
定理
$$ 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} $$ これが$7$の倍数なら、$[a_{n} a_{n-1} … a_{1} a_{0}]$も$7$の倍数で、 $$ 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} $$ これが$13$の倍数なら、$[a_{n} a_{n-1} … a_{1} a_{0}]$も$13$の倍数だ。
説明
これがどういう意味かというと、各桁の数を3つずつグループにして、交代で足したり引いたりした数が$7$の倍数なら、元の数も7の倍数だってことだ。例を見て理解してみよう。
例えば、$745444$を見れば、判定法によって $$ 745-444=7 \cdot 301 $$ で7の倍数だけど、実際に$745444$は$745444=7 \cdot 106492$で$7$の倍数だ。もっと大きな数の$11794545$を見ても、上の判定法はまだしっかりと当てはまってて、 $$ -11+794-545 = 238 = 7 \cdot 34 $$ は$7$の倍数で、実際には$11794545$も$11794545=7 \cdot 1684935$で$7$の倍数だ。
この定理は$13$の場合にも成立して、実は$11$の場合にも成立する。その理由は$7$の倍数判定法と$11$の倍数判定法と$13$の倍数判定法が全部同じ証明から出てくるからだ。数字を変えただけで完全に同じ証明なので、$11$の場合と$13$の場合は省略するよ。
証明
ストラテジー：証明自体はとても基本的なテクニックのみを使っているが、本質的に長くてアイデアも必要だから簡単ではない。キーとなるアイデアは、$1001$と$999999$が$7$の倍数であるという事実を使うことだ。 $$ 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 $$
$$ \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*} $$
括弧で囲み部分だけを見れば、
$$ \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*} $$
つまり、 $$ ([a_{n} a_{n-1} a_{n-2}]-[a_{n-3} a_{n-4} a_{n-5}]) $$ これが$7$の倍数なら、 $$ [a_{n} a_{n-1} a_{n-2} a_{n-3} a_{n-4} a_{n-5}] $$ も$7$の倍数だ。 さて、一般化してみよう。
$$ \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*} $$
ここで、$[a_{n} a_{n-1} a_{n-2}]7\cdot 143\cdot 10^{n-5}$のような項を全部$7$でグループ化して、$c$として表せば、
$$ \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*} $$
$c$が何であれ、$7c$は確実に$7$の倍数なので、ここで後半部分が$7$の倍数なら証明は完了する。そして、ここで$999999$の性質が使われる。
$$ \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*} $$
上の式が成り立つので、$10$の累乗は、$7$で割り切れる定数項を出し、次数を$6$ずつ減らしていける。
$$ \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, … ,0$はすべて$6$の倍数なので、
$$ \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*} $$
従って、
$$ [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}] $$
これが$7$の倍数なら、$[a_{n} a_{n-1} … a_{1} a_{0}]$も$7$の倍数だ。
$1001 = 7 \cdot 143 = 7 \cdot 11 \cdot 13$という点を考えると、$11$であれ$13$であれ、証明はもう終わっているも同然だ。
■