logo

11の倍数判定法のより簡単な証明 📂整数論

11の倍数判定法のより簡単な証明

ビルドアップ

このポストでは基数に関する便宜のために次のような表記を使用する。 [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*}

定理

an−an−1+…+a1−a0a_{n} - a_{n-1} + … + a_{1} - a_{0}が1111の倍数ならば、[anan−1…a1a0][a_{n} a_{n-1} … a_{1} a_{0}]も1111の倍数である。

説明

もちろん、77の倍数の判定法と1313の倍数の判定法から、与えられた数が77、1111、1313の倍数であるかを判断する方法を得ることができるが、1111の場合には、はるかに簡単な結果とシンプルな証明がある。しかし、77、1111、1313のケースと異なり、合同式を使用するため、非常に基礎的な整数論の知識が証明を理解するためには必要である。

証明

戦略：証明で使われるキー・アイデアは、モジュロ1111で、1010と−1-1が合同であることだ。このヒントだけがあれば、証明は実質的に完了したも同然だ。 10≡−1(mod11) 10 \equiv -1 \pmod {11}

[anan−1…a1a0]≡an⋅10n+an−1⋅10n−1+…+a1⋅101+a0⋅100(mod11)≡an(−1)n+an−1(−1)n−1+…+a1(−1)1+a0(−1)0(mod11)≡an−an−1+an−2−…+a2−a1+a0(mod11) \begin{align*} & [a_{n} a_{n-1} … a_{1} a_{0}] \\ \equiv & a_{n} \cdot 10^{n} + a_{n-1} \cdot 10^{n-1} +…+ a_{1} \cdot 10^{1} + a_{0} \cdot 10^{0} \pmod {11} \\ \equiv & a_{n} {(-1)}^{n}+ a_{n-1} {(-1)}^{n-1}+…+ a_{1} {(-1)}^{1}+ a_{0} {(-1)}^{0} \pmod {11} \\ \equiv & a_{n} - a_{n-1} + a_{n-2} -…+ a_{2} - a_{1} + a_{0} \pmod {11} \end{align*} つまりan−an−1+an−2−…+a2−a1+a0a_{n} - a_{n-1} + a_{n-2} -…+ a_{2} - a_{1} + a_{0}が1111の倍数ならば、 an−an−1+an−2−…+a2−a1+a0≡0≡[anan−1…a1a0](mod11) a_{n} - a_{n-1} + a_{n-2} -…+ a_{2} - a_{1} + a_{0} \equiv 0 \equiv [a_{n} a_{n-1} … a_{1} a_{0}] \pmod {11} すなわち、[anan−1…a1a0][a_{n} a_{n-1} … a_{1} a_{0}]は11の倍数である。

■