整数がｘの倍数であるか否かを判定する方法は，中学数学の問題だと思うが，

［１］ｘ＝２：１の位が０，２，４，６，８

［２］ｘ＝３：各位の数の和が３の倍数

［３］ｘ＝４：下２桁が４の倍数（１００は４の倍数だから）

［４］ｘ＝５：１の位が０，５

［５］ｘ＝６：１の位が０，２，４，６，８かつ各位の数の和が３の倍数

［６］ｘ＝８：下３桁が８の倍数（１０００は８の倍数だから）

［７］ｘ＝９：各位の数の和が９の倍数

［８］ｘ＝１０：１の位が０

［９］ｘ＝１２：下２桁が４の倍数かつ各位の数の和が３の倍数

　７の倍数，１１の倍数，１３の倍数であることの判定法はあるにはあるのだが煩わしいし，一目見てわかるものではない．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

【１】不思議な数１００１

　ところで，１００１＝７・１１・１３は連続する３つの素数の積になっている不思議な数である．最初のの３つの素数２，３，５では割り切れず，次の３つの素数７，１１，１３で割り切れる．

　１０００＝−１（ｍｏｄ７・１１・１３＝１００１）

この１００１を繰り返して使うと，１０進法で７の倍数，１３の倍数を判定できる．

　すなわち，整数ａがあったとき，１００１をどんどん引いていけば最終的には１０００以下の整数ｂになる．この整数ｂが７の倍数，１３の倍数のとき，整数ａも７の倍数，１３の倍数である．したがって，３桁の整数が７の倍数，１３の倍数であることが判定できればよいことになる．

　　Ｐ＝ａ3・１０^2＋ａ2・１０＋ａ1

において，

　　Ｐ＝２ａ3＋３ａ2＋ａ3　　　（ｍｏｄ７）

　　Ｐ＝ａ3−ａ2＋ａ3　　　　　（ｍｏｄ１１）

　　Ｐ＝−４ａ3−３ａ2＋ａ3　　（ｍｏｄ１３）

［１］３桁の数が７の倍数であるためには２ａ3＋３ａ2＋ａ3が７の倍数になることが必要十分である．

［２］３桁の数が１３の倍数であるためには−４ａ3−３ａ2＋ａ3が１３の倍数になることが必要十分である．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

【２】素数による整除性

［３］奇数番目の桁の数の和と偶数番目の桁の数の和との差が１１の倍数のとき，そのときに限り１１の倍数である．

　素数７による整除性について補足しよう．与えられた数を

　　Ｐ＝ａn・１０^(n-1)＋ａn-1・１０^(n-2)＋・・・＋ａ2・１０＋ａ1

とする．

［４］１の位の数を除去し，残った数から除去した数の２倍を引く．

　　Ｑ＝ａn・１０^(n-2)＋ａn-1・１０^(n-3)＋・・・＋ａ2−２ａ1

この数が７で割り切れるとき，そのときに限り元の数Ｐは７で割り切れる．（この数が大きすぎる場合は，この操作を何度でも繰り返すことができる）

　この操作の意味を考えてみると

　　Ｐ−１０Ｑ＝２１ａ1＝７・３ａ1

より，７の倍数を元の数から引くことを意味している．したがって，残った数が７で割り切れれば，元の数も７で割り切れることになる．

　元の数の桁が非常に多い場合が下３桁を除去し残りから引くことで処理がずっと高速化される．

　　Ｑ＝ａn・１０^(n-4)＋ａn-1・１０^(n-5)＋・・・＋ａ4−（ａ3・１０^2＋ａ2・１０＋ａ1）

　　Ｐ−１０００Ｑ＝１００１（ａ3・１０^2＋ａ2・１０＋ａ1）＝７・１１・１３（ａ3・１０^2＋ａ2・１０＋ａ1）

この操作の正当性は１００１が７で割り切れることからきているのである．

［５］下３桁の数を除去し，残った数から除去した数を引く．この数が７で割り切れるとき，そのときに限り元の数は７で割り切れる．

−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−

　素数１３による整除性のためには，

［６］１の位の数を除去し，残った数から除去した数の９倍を引く．

　　Ｑ＝ａn・１０^(n-2)＋ａn-1・１０^(n-3)＋・・・＋ａ2−９ａ1

この数が１３で割り切れるとき，そのときに限り元の数Ｐは１３で割り切れる．（この数が大きすぎる場合は，この操作を何度でも繰り返すことができる）

　この操作の意味を考えてみると

　　Ｐ−１０Ｑ＝９１ａ1＝１３・７ａ1

より，１３の倍数を元の数から引くことを意味している．したがって，残った数が１３で割り切れれば，元の数も１３で割り切れることになる．

　元の数の桁が非常に多い場合が下３桁を除去し残りから引くことで処理がずっと高速化される．

　　Ｑ＝ａn・１０^(n-4)＋ａn-1・１０^(n-5)＋・・・＋ａ4−（ａ3・１０^2＋ａ2・１０＋ａ1）

　　Ｐ−１０００Ｑ＝１００１（ａ3・１０^2＋ａ2・１０＋ａ1）＝７・１１・１３（ａ3・１０^2＋ａ2・１０＋ａ1）

この操作の正当性は１００１が１３で割り切れることからきているのである．

［７］下３桁の数を除去し，残った数から除去した数を引く．この数が１３で割り切れるとき，そのときに限り元の数は１３で割り切れる．

−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−

　素数１７による整除性のためには，

［８］１の位の数を除去し，残った数から除去した数の５倍を引く．

　　Ｑ＝ａn・１０^(n-2)＋ａn-1・１０^(n-3)＋・・・＋ａ2−５ａ1

この数が１７で割り切れるとき，そのときに限り元の数Ｐは１７で割り切れる．（この数が大きすぎる場合は，この操作を何度でも繰り返すことができる）

　この操作の意味を考えてみると

　　Ｐ−１０Ｑ＝５１ａ1＝１７・３ａ1

より，１７の倍数を元の数から引くことを意味している．したがって，残った数が１７で割り切れれば，元の数も１７で割り切れることになる．

　以下，

［９］素数１９による整除性のためには，１の位の数を除去し，残った数から除去した数の１７倍を引く．１７１＝１９・９

［１０］素数２３による整除性のためには，１の位の数を除去し，残った数から除去した数の１６倍を引く．１６１＝２３・７

［１１］素数２９による整除性のためには，１の位の数を除去し，残った数から除去した数の２６倍を引く．２６１＝２９・９

［１２］素数３１による整除性のためには，１の位の数を除去し，残った数から除去した数の３倍を引く．３１＝３１

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝