■素数定理とエラトステネスのふるい(その5)

 ところで,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の倍数になることが必要十分である.

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