倍数判定式の作り方

ある数10m+nがあります。m,nは整数です。
これが任意の整数Aの倍数かどうかを判定する式を作りたいとき、どうするか。



たとえば7の倍数判定だったらA=7で

-m+2nが7の倍数だったら10m+nも7の倍数


13の倍数判定だったらA=13で
m+4nが13の倍数だったら10m+nも13の倍数なんですが、
この4とか-2とか、Aを一般化したいわけです。



10m+n=A*z1
B2*m+B1*n=A*z2


としてみましょう。
(z1,z2、B1,B2も整数です)


1つ目の式を変形して、
n=A*z1-10m
このnを2つ目の式に代入して

B2*m+B1*(A*z1-10m)=A*z2
展開して
B2*m+A*B1*z1-10m*B1=A*z2

mを含む項と含まない項に分け
B2*m-10m*B1=A*z2-A*B1*z1

(B2-10B1)*m=A*(z2-B1*z1)


こうした上で、A=7だったら
B2=-1、B1=2とすると、左辺のカッコの中が-1-10*2=-21になって、両辺が7で約分できるので、判定式として成立します。

同様にA=13だったら
B2=1、B1=4とすると、左辺のカッコの中が1-10*4=-39になるため、両辺が13で約分できて、これも判定式として成立します。


つまり、以下の形に変形することにより、任意のAに対して

(B2-10B1)*m=A*(z2-B1*z1)

B2とB1を定めやすくなる、というわけです。

ためしにA=4だと
B1=1、B2=6とか
B2=2、B1=-1とかで成立します。

32が4の倍数だと判別するために、後者を採用すると
下1桁2から、それ以外3に2をかけて6にして引き算
-4になってこれは4の倍数なので、元の数32も4の倍数と、ちゃんとできています。



A=3だったら

B1=1、B2=1とすると
たとえば36だったら下1桁6とそれ以外3を足した9が3の倍数だったら、元の数36も3の倍数


A=11だったら
B2=-1、B1=1
121を相手にしてみると
下1桁1からそれ以外12を引いて11なので、元の121も11の倍数


とできます。



任意の数の倍数判定に使うことができます。
が、速度は遅いし、あまり役に立たないです。
2のべき乗と3のべき乗と5のべき乗と11のべき乗などを区別しません。

ですので、2や5のべき乗の倍数判定(十進数)では必ず割り切れるのでほとんど意味がありませんし

3や9の倍数判定、「各桁を足す」に対して、完全下位互換となりますし(おそろしく遅い)
11の倍数判定「偶数桁の合計と奇数桁の合計を引く」に対しても完全下位互換になります。



たとえば1053が3の倍数だということを確かめたい場合、
1+5+3=9なのですぐにわかりますが、今回の方法では

105と3を足した108が3の倍数か知るために8に10を足した18が3の倍数か知るために
1+8=9と、数珠つなぎのような地獄を味わうことになり、大変判定が遅くなります。



なお、ある数Aの倍数判定のための式は1つではなく、無数に作りだすことができます



100m3+10m2+m1とかにしたらどうなるんでしょうね？