■1001(その19)

 整数を1000進法で表した場合

  P=an・1000^(n-1)+an-1・1000^(n-2)+・・・+a1

その数が37で割り切れるかどうかの判定法は,1000=1(mod37)より

  P=an+an-1+・・・+a1  (mod37)

各位の数の和が37の倍数のとき,そのときに限り37の倍数である.

 また,1000=−1(mod7・11・13=1001)より

  P=(a1+a3+・・・)−(a2+a4+・・・)  (mod7・11・13)

奇数番目の桁の数の和と偶数番目の桁の数の和との差が7,11,13の倍数のとき,そのときに限りその数のの倍数である.

===================================

 ところで,1001=7・11・13は連続する3つの素数の積になっている不思議な数である.この1001を繰り返して使うと,10進法で7の倍数,13の倍数を判定できる.

 すなわち,整数aがあったとき,1001をどんどん引いていけば最終的には1000以下の整数bになる.この整数bが7の倍数,13の倍数のとき,整数aも7の倍数,13の倍数である.したがって,3桁の整数が7の倍数,13の倍数であることが判定できればよいことになる.

  P=a3・10^2+a2・10+a1

において,

  P=2a3+3a2+a3   (mod7)

  P=a3−a2+a3     (mod11)

  P=−4a3−3a2+a3  (mod13)

3桁の数が7の倍数であるためには2a3+3a2+a3が7の倍数になることが必要十分である.

3桁の数が13の倍数であるためには−4a3−3a2+a3が13の倍数になることが必要十分である.

===================================