素数による整除性について調べてみよう．

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

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

　ある整数から１００１をどんどん引いていけば最終的には１０００以下の整数になる．この整数

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

において

［２］３桁の数が７の倍数であるためには２ａ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）

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

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

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