17の倍数の判定法

こちらの続きの内容です。

定理　ある数が１7の倍数であるためには、一の位から左へ８桁ごとに区切り、奇数番目の区画にある８桁以下の数の和と、偶数番目の区画にある８桁以下の数の和との差が１７の倍数であることが必要十分条件となる。

証明

$10 \equiv 10 \mod 17$

$10^{2} =100 \equiv 15 \mod 17$

$10^{3} =10^{2} \times 10 \equiv 15 \times 10 =150 \equiv 14 \mod 17$

$10^{4} =10^{3} \times 10 \equiv 14 \times 10 =140 \equiv 4 \mod 17$

$10^{5} =10^{4} \times 10 \equiv 4 \times 10 = 40 \equiv 6 \mod 17$

$10^{6} =10^{5} \times 10 \equiv 6 \times 10 = 60 \equiv 9 \mod 17$

$10^{7} =10^{6} \times 10 \equiv 9 \times 10 = 90 \equiv 5 \mod 17$

$10^{8} =10^{7} \times 10 \equiv 5 \times 10 = 50 \equiv -1 \mod 17$

より、n≧1に対して、下記が成立するためです。

$10^{8n} \equiv \left(-1\right)^{n} \mod 17$

例題　189741323725687418282725が１７の倍数であるか判定せよ。

解答　一の位から左へ８桁ごとに区切り、奇数番目の区画にある８桁以下の数の和と、偶数番目の区画にある８桁以下の数の和との差を求めると、

$(18282725+18974132)-37256874=-17$

となり、17の倍数となるため、元の数も17の倍数となります。　

※　13の倍数の判定法については、下記の参考書などを参考にしてみてください。

７の倍数の判定法と同様です。