十進法2

おそらく、多くの人が小中学生のときに習うと思うのだが
ある数字がnの倍数かどうかを簡単に見分ける方法というのがある。
例えば3の倍数かどうか知りたければ全ての位の数字を足す。
その結果が3の倍数なら、元の数も3の倍数となる。というやつだ。
（ちなみにこれは再帰的に使えるので、
結果が二桁以上ならまた全ての位の数字を足すということを繰り返せばよい）

知ってる限りをまとめると
A.2の倍数……1の位が2の倍数ならＯＫ
B.3の倍数……上記の方法
C.4の倍数……下二桁を取り出してそれが4の倍数ならＯＫ
D.5の倍数……1の位が5の倍数ならＯＫ
E.9の倍数……3の倍数と同じような手法
F.10の倍数……1の位が0ならＯＫ

というところになりますわな。
でもこの法則も、十進法で記述していることが前提になってます。
一般論で考えるとすると……m進法として……
Fはどの場合にも成立します。
これはあたりまえ。m進法で数えていてmの倍数かどうかはすぐわかる。
そしてA.とC.とD.は同じタイプです。
具体的に十進法を例に取ると、
10=2*5だから、下一桁を見るだけで2の倍数か、5の倍数かどうかすぐにわかる。
10^2=100=4*25だから、下二桁を見るだけで4の倍数か、25の倍数かどうかすぐにわかる。
10^3=1000=8*125だから、下三桁を見るだけで…
と続いていきます。
B.とE.が難しくて、これは（mの累乗）-1が共通の因数を持てば使えます。
これまた十進法を例に取ると
10=9+1=3*3+1
100=99+1=3*33+1
1000=999+1=3*333+1
というように、10の累乗-1が全て3の倍数になってるので
984=900+80+4=9*100+8*10+4=9*(99+1)+8*(9+1)+4=3の倍数+9+8+4
というように分解できるわけですな。

この「（mの累乗）-1が共通の因数を持つ」
っていうのは実はどのmでも成立します。
m^r-1はかならずm-1を因数に持つんですよ（高校の数学を思い出すなー）。
つまり、（mの累乗）-1は必ずm-1という共通因数を持つので
m進法で、ある数がm-1の倍数かどうかは全ての位の数字を足せば分かるわけです。
十進法の場合は特にm-1=10-1=9が3の倍数なので
3の倍数かどうかの判定もできることになります。
そうしてみると、
何進法で数えると、一番楽に倍数を判定できるか
というのが頑張れば編み出せそうですね。

俺はメンドイのでパス。