1. 概要

例えば、「十進数で $553$ は $9$ で割り切れるか？」という問題があったとします。

正解は「割り切れない」です。

この程度の大きさの数ならちょっと時間をかければ暗算で解けますし、気の利いた人ならもっと短時間でこう答えるでしょう。

$5 + 5 + 3 = 13$ で、$13$ は $9$ で割り切れないから「割り切れない」

では、「$587384467$ が $3$ で割り切れるか」ではどうでしょう。

暗算はつらいかもしれませんが、電卓があれば一発でしょう。
何らかのプログラミング言語上で計算する場合でも、整数の剰余を計算すればすぐにわかります。

それでは、以下の自然数が $7$ で割り切れるかどうかについてはどうでしょうか。(非常に長いため横スクロールします)

$23681956398322870200090570207995386728031540078050054324059168094515090950861839430672113370780988298554969343424270384705353956782138138024826769352862729778299935169885977474105892233291441671107040819687702059409396113957155769446585440948609686607145310943569208424808375990254402725457230285412648639995$

こんな長い数を扱える電卓は身近にはめったにありませんが、多倍長整数がサポートされているプログラミング言語であれば計算することができます。
例えば、.NETの場合は BigIteger 構造体を使って以下のようなコードを書けば正解がわかります。

var value = BigInteger.Parse("23681956398322870200090570207995386728031540078050054324059168094515090950861839430672113370780988298554969343424270384705353956782138138024826769352862729778299935169885977474105892233291441671107040819687702059409396113957155769446585440948609686607145310943569208424808375990254402725457230285412648639995");
var result = value % 7 == 0;

ですが、長い数の剰余を計算するのにはそれなりに時間がかかりますので、少しでも性能を稼ぎたい場合には別の方法を探したいところです。

本稿では、任意の長さの自然数が別の自然数で割り切れるかどうかを高速に判別する方法について述べます。

需要が非常に限られていて、かつご存じの方はご存じの知識だとは思いますが、筆者が~~趣味で~~調べて納得できる結論に達するまでそれなりに時間をかけてしまったので、備忘録として投稿しておきます。

2. まずは九去法とその根拠から

2.1 九去法とは

九去法とは要するに前述の「$5 + 5 + 3 = 13$ で、$13$ は $9$ で割り切れないから『割り切れない』」という回答で用いた計算手段です。

では、そもそもどうしてそういう計算が成立するのでしょうか?

2.２九去法の根拠

ここから少々難しい用語が出てきますが、言っていることは簡単です。~~多分。~~

合同式という数式の書き方があります。

例えば、こんな感じです。

13 \equiv 4 \pmod 9

これが意味するのは、「$13$ を $9$ で割った余りと $4$ を $9$ で割った余りは等しい」ということです。この場合の $9$ を 「法」 と言います。

合同式には以下の性質があります。(本来はもっとありますが本稿の趣旨からは外れるので省略します)

$a \equiv b \pmod{N}$ かつ $c \equiv d \pmod{N}$ であるとき、$a + c\equiv b + d \pmod{N}$
$a \equiv b \pmod{N}$ かつ $c \equiv d \pmod{N}$ であるとき、$a - c\equiv b - d \pmod{N}$
$a \equiv b \pmod{N}$ かつ $c \equiv d \pmod{N}$ であるとき、$a \cdot c\equiv b \cdot d \pmod{N}$

また、以下の法則も成立します。

$a \equiv b \pmod{N_1} $ かつ $N_1 \equiv 0 \pmod{N_2}$ であるとき、$a \equiv b \pmod{N_2}$

[証明]

既存の証明方法を探してみたのですが、見つけることができなかったので自分で証明しました。数学は専門外なので、多少の怪しい表記はご容赦ください。証明自体は合っているはずです。~~多分…~~

一般的に、任意の自然数 $a$ と $b$ は以下のように一意に表現できる。

a = a_1 \cdot N_1 + a_2, 0 \leqq a_2 < N_1 \tag{1}

b = b_1 \cdot N_1 + b_2, 0 \leqq b_2 < N_1 \tag{2}

前提条件から $a \equiv b \pmod{N_1}$ であるので、$(1)$と$(2)$から以下の合同式が成立する。

a_1 \cdot N_1 + a_2 \equiv b_1 \cdot N_1 + b_2  \pmod{N_1} \tag{3}

$N_1 \equiv 0 \pmod{N_1}$ なので、$(3)$を以下のように変形できる。

a_2 \equiv b_2  \pmod{N_1} \tag{4}

$0 \leqq a_2 < N_1$ かつ $0 \leqq b_2< N_1$ なので、以下の等式が成立する。

a_2 = b_2 \tag{5}

一方、前提条件より $N_1 \equiv 0 \pmod{N_2}$ であることから、$N_1 = k \cdot N_2$ と一意に表現できる。

これを利用すると $(1)$ と $(2)$ は以下のように変形できる。

a = a_1 \cdot k \cdot N_2  + a_2 \tag{6}

b = b_1 \cdot k \cdot N_2  + b_2 \tag{7}

$(6)$と($7)$を$N_2$を法とした合同式で表現する。

a \equiv a_1 \cdot k \cdot N_2 + a_2 \equiv a_2 \pmod{N_2} \tag{8}

b \equiv b_1 \cdot k \cdot N_2  + b_2 \equiv b_2 \pmod{N_2} \tag{9}

$(5)$, $(8)$, $(9)$ より、以下の合同式が成立する。

a \equiv b \pmod{N_2}

(証明終了)

例えば、$N_1$ が $10$ で $N_2$ が $5$ の場合は $10 \equiv 0 \pmod{5}$ なので、$a \equiv b \pmod{10}$ のときは必ず $a \equiv b \pmod{5}$ となります。

一方、先ほどの問題に出てきた $553$ という数字は、各桁の数字をばらばらにして以下の等式で表現できます。

553 = 5 \cdot 10^2 + 5 \cdot 10^1 + 3 \cdot 10^0

この等式を $10$ より $1$ だけ少ない数である $9$ を法とした合同式で表現してみます。($9$が$10$より$1$だけ少ないというのがミソです)

553 \equiv 5 \cdot 10^2 + 5 \cdot 10^1 + 3 \cdot 10^0 \pmod{9}

ここで、$10$のべき乗を分解してみます。

553 \equiv 5 \cdot 10 \cdot 10 + 5 \cdot 10 + 3 \cdot 1 \pmod{9}

$10 \equiv 1 \pmod{9}$ なので、これを利用して前の式を変形します。

553 \equiv  5 \cdot 1 \cdot 1 + 5 \cdot 1 + 3 \cdot 1 \equiv 5 + 5 + 3   \pmod 9

つまり、$553$ を $9$ で割った余りは $5 + 5 + 3$ を $9$ で割った余りに等しい、ということです。

非常に大雑把ですが、これで九去法の根拠を説明できました。

この方法をより一般的に述べると、以下のようになります。

a \equiv (a をN進数で表現した場合の各桁の値の総和) \pmod{N-1}

3. プログラミング言語での応用

前述したように、一般的に以下の合同式が成立します。

\displaylines{
任意の自然数 a において、\\
a \equiv (a をN進数で表現した場合の各桁の値の総和) \pmod{N-1}\tag{A}
}

\displaylines{
任意の自然数 a および b において、\\
a \equiv b \pmod{N_1} かつ N_1 \equiv 0 \pmod{N_2} であるとき、\\
a \equiv  b \pmod{N_2} \tag{B}
}

通常であれば数の基数の変換は結構な作業になるのですが、ビット単位の演算 (シフトや AND ) が充実しているプログラミング言語であれば、$N$ として $2$ のべき乗を選ぶことによって計算コストを大きく減らすことが出来ます。

例えば、任意の長さの自然数 $a$ を $5$ で割った余りを計算したいとします。
10進数であれば最下位の1桁を見てすぐわかるのですが、コンピュータでの計算は基本的に2進数ベースなので、すぐにはわからないはずです。

まず、$2^n - 1$ が $5$ の倍数である $n$ を探します。
この条件を満たす最小の $n$ は $4$ です。($2^4 - 1 = 16 - 1 = 15$)
次に自然数 $a$ を $2^n$ (= $2^4$ = $16$) 進数に変換するのですが、わかりやすくするために2進数で表記します。
例えば、$a$ を $57825$ として、2 進数で表すとこんな感じです。

(下位側) 1000011110000111  (上位側) \tag{1}

これを下位から $n$ (= $4$) 桁毎に区切って、更にそれぞれの桁を 0 ～ 15 の整数で表します。

(下位側) 1000 : 0111 : 1000 : 0111  (上位側) \tag{2}

(下位側) 1 : 14 : 1 : 14  (上位側) \tag{3}

$(A)$ と $(3)$ から以下の合同式が成立します。

57825 \equiv 1 + 14 + 1  + 14 \equiv  30 \pmod{15} \tag{4}

更に、$15 \equiv 0 \pmod{5}$ であるので、$(B)$ と $(4)$ から以下の合同式も成立します。

57825 \equiv 30 \pmod{5} \tag{5}

$30 \equiv 0 \pmod{5}$ なので、$(5)$ から $57825 \equiv 0 \pmod{5}$ であることが分かります。
これで、$57825$ は $5$ で割り切れることがわかりました。

ここまでで必要な演算は以下の通りです。剰余の計算は最後にしか使用していません。

$(3)$ で各桁の値を求めるためのビットシフトとマスク
$(4)$ で各桁の総和を求めるための加算
$(5)$ で余りを求めるための剰余の計算

ここでは計算方法を説明するために $57825$ というあまり大きくない数を使用しましたが、例えば長さが $1024$ ビットの自然数だとどうなるでしょうか。
.NET の BigInteger の場合、1024 ビット整数の剰余を求めるためには BigInteger の内部で少なくとも以下の演算が必要です。

およそ $1024/32$ ( = 32) 回の 64ビット整数 $\div$ 32 ビット整数の除算
およそ $(1024/32) * (1024/32-1) / 2$ (= 496) 回の 64 ビット整数同士の減算

一方、前述したような各桁を加算する方法だと以下の演算が必要になります。

およそ $1024 / 4$ (=256) 回の 4 ビット整数のビットシフトとマスク
およそ $1024 / 4 - 1$ (=255) 回の int に対する加算
1 回の int に対する剰余の計算

除算にかかる時間を考えると、単純に 1024 ビット整数の剰余を計算するよりもかなりの高速化が見込めます。
また、与えられた整数が長いほど計算時間の差が大きくなることが予想できます。

4. 具体例

4.1 2 のべき乗で割り切れるかどうかを調べる

ある自然数 $a$ が $2^n$ $(n \geqq 1)$ で割り切れるかは、$a$ の下位 $n$ ビットがすべて $0$ であることを確認することで調べることが出来ます。

むしろ、$2^n - 1$ は必ず奇数になるので、本稿で述べたアルゴリズムを利用することはできません。

4.2 3 で割り切れるかどうかを調べる

$2^n - 1$ が $3$ の倍数となる最小の $n$ は $2$ なので、以下の手順で計算できます。

計算対象の整数を下位から $2$ ビットずつに区切る。
各桁の総和を計算する。
総和を $3$ で割った余りが 0 かどうかを調べる。

ただし、$n = 8$ にすることもできます。何故ならば $2^8-1$ (= 255) も $3$ の倍数だからです。
コンピュータのメモリの最小のアクセス単位は通常 8 ビットなので、$n = 8$ とすることによってビットシフトおよびマスクの回数がおよそ $1/4$ になるメリットがあります。
更に、計算対象の整数がバイト配列で与えられている場合は、ビットシフトとマスクの手間をまるごと省略できるので、より高速化が見込めます。

4.3 5 で割り切れるかどうかを調べる

$2^n - 1$ が $5$ の倍数となる最小の $n$ は $4$ なので、以下の手順で計算できます。

計算対象の整数を下位から $4$ ビットずつに区切る。
各桁の総和を計算する。
総和を $5$ で割った余りが 0 かどうかを調べる。

ただし、$n = 8$ にすることもできます。何故ならば $2^8-1$ (= 255) は $5$ の倍数だからです。
コンピュータのメモリの最小のアクセス単位は通常 8 ビットなので、$n = 8$ とすることによってビットシフトおよびマスクの回数がおよそ $1/2$ になるメリットがあります。
更に、計算対象の整数がバイト配列で与えられている場合は、ビットシフトとマスクの手間をまるごと省略できるので、より高速化が見込めます。

4.4 2 のべき乗ではない偶数で割り切れるかどうかを調べる

ある任意の長さの自然数 $a$ が別の偶数 $b$ で割り切れるかどうかを調べたい場合、まず $b$ を以下のように分解します。

b = b_1 \cdot 2^m, ただし b_1 は 3 以上の奇数、かつ m \geqq 1

その後、以下の条件を満たすかどうかを調べます。

$b$ が $2^m$ で割り切れる、かつ
$b$ が $b_1$ で割り切れる。

$b$ が $2^m$ で割り切れるかどうかを調べる方法については 4.1 2 のべき乗で割り切れるかどうかを調べるを参照してください。

$b$ が $b_1$ で割り切れるかどうかを調べる方法については 4.6 一般的な奇数で割り切れるかどうかを調べるを参照してください。

4.5 一般的な奇数で割り切れるかどうかを調べる

ある任意の長さの自然数 $a$ が別の奇数 $b$ $(b \geqq 3)$ で割り切れるかどうかを調べる手順は以下の通りです。

$2^n - 1$ が $b$ の倍数となる $n$ を選ぶ。
$a$ の下位から $n$ ビットずつに区切る。
各桁の総和を計算する。
総和を $b$ で割った余りが 0 かどうかを調べる。

4.2 3 で割り切れるかどうかを調べるおよび 4.3 5 で割り切れるかどうかを調べるで述べたように、$n$は必ずしも小さい方が有利というわけではないことに注意してください。

参考として、$b$ で割り切れるかどうか調べるために利用できる $n$ のリストを以下に挙げておきます。

[任意の自然数 $a$ が奇数 $b$ で割り切れるかどうかを調べるための $n$ のリスト]

$b$ $(3 \leqq b \leqq 4,294,967,295 )$	$(2^n -1) \equiv 0 \pmod{b} を満たす n$ $(2 \leqq n \leqq 32)$
$3$	$2,$ $4,$ $6,$ $8,$ $10,$ $12,$ $14,$ $16,$ $18,$ $20,$ $22,$ $24,$ $26,$ $28,$ $30,$ $32$
$5$	$4,$ $8,$ $12,$ $16,$ $20,$ $24,$ $28,$ $32$
$7$	$3,$ $6,$ $9,$ $12,$ $15,$ $18,$ $21,$ $24,$ $27,$ $30$
$9$	$6,$ $12,$ $18,$ $24,$ $30$
$11$	$10,$ $20,$ $30$
$13$	$12,$ $24$
$15$	$4,$ $8,$ $12,$ $16,$ $20,$ $24,$ $28,$ $32$
$17$	$8,$ $16,$ $24,$ $32$
$19$	$18$
$21$	$6,$ $12,$ $18,$ $24,$ $30$
$23$	$11,$ $22$
$25$	$20$
$27$	$18$
$29$	$28$
$31$	$5,$ $10,$ $15,$ $20,$ $25,$ $30$
$33$	$10,$ $20,$ $30$
$35$	$12,$ $24$
$39$	$12,$ $24$
$41$	$20$
$43$	$14,$ $28$
$45$	$12,$ $24$
$47$	$23$
$49$	$21$
$51$	$8,$ $16,$ $24,$ $32$
$55$	$20$
$57$	$18$
$63$	$6,$ $12,$ $18,$ $24,$ $30$
$65$	$12,$ $24$
$69$	$22$
$73$	$9,$ $18,$ $27$
$75$	$20$
$77$	$30$
$85$	$8,$ $16,$ $24,$ $32$
$87$	$28$
$89$	$11,$ $22$
$91$	$12,$ $24$
$93$	$10,$ $20,$ $30$
$99$	$30$
$105$	$12,$ $24$
$113$	$28$
$117$	$12,$ $24$
$119$	$24$
$123$	$20$
$127$	$7,$ $14,$ $21,$ $28$
$129$	$14,$ $28$
$133$	$18$
$145$	$28$
$151$	$15,$ $30$
$153$	$24$
$155$	$20$
$165$	$20$
$171$	$18$
$189$	$18$
$195$	$12,$ $24$
$205$	$20$
$215$	$28$
$217$	$15,$ $30$
$219$	$18$
$221$	$24$
$231$	$30$
$233$	$29$
$241$	$24$
$255$	$8,$ $16,$ $24,$ $32$
$257$	$16,$ $32$
$267$	$22$
$273$	$12,$ $24$
$275$	$20$
$279$	$30$
$315$	$12,$ $24$
$331$	$30$
$337$	$21$
$339$	$28$
$341$	$10,$ $20,$ $30$
$357$	$24$
$381$	$14,$ $28$
$399$	$18$
$435$	$28$
$451$	$20$
$453$	$30$
$455$	$12,$ $24$
$465$	$20$
$511$	$9,$ $18,$ $27$
$513$	$18$
$565$	$28$
$585$	$12,$ $24$
$595$	$24$
$601$	$25$
$615$	$20$
$635$	$28$
$645$	$28$
$651$	$30$
$657$	$18$
$663$	$24$
$683$	$22$
$693$	$30$
$723$	$24$
$765$	$24$
$771$	$16,$ $32$
$775$	$20$
$819$	$12,$ $24$
$825$	$20$
$889$	$21$
$993$	$30$
$1,023$	$10,$ $20,$ $30$
$1,025$	$20$
$1,057$	$15,$ $30$
$1,071$	$24$
$1,103$	$29$
$1,105$	$24$
$1,197$	$18$
$1,205$	$24$
$1,247$	$28$
$1,271$	$20$
$1,285$	$16,$ $32$
$1,353$	$20$
$1,359$	$30$
$1,365$	$12,$ $24$
$1,387$	$18$
$1,533$	$18$
$1,547$	$24$
$1,661$	$30$
$1,687$	$24$
$1,695$	$28$
$1,705$	$20$
$1,785$	$24$
$1,801$	$25$
$1,905$	$28$
$1,953$	$30$
$1,971$	$18$
$1,989$	$24$
$2,047$	$11,$ $22$
$2,049$	$22$
$2,089$	$29$
$2,169$	$24$
$2,255$	$20$
$2,317$	$30$
$2,325$	$20$
$2,359$	$21$
$2,387$	$30$
$2,731$	$26$
$2,979$	$30$
$3,069$	$30$
$3,075$	$20$
$3,133$	$24$
$3,171$	$30$
$3,277$	$28$
$3,315$	$24$
$3,591$	$18$
$3,615$	$24$
$3,641$	$30$
$3,683$	$28$
$3,741$	$28$
$3,813$	$20$
$3,855$	$16,$ $32$
$4,095$	$12,$ $24$
$4,097$	$24$
$4,161$	$18$
$4,369$	$16,$ $32$
$4,599$	$18$
$4,641$	$24$
$4,681$	$15,$ $30$
$4,859$	$28$
$4,983$	$30$
$5,061$	$24$
$5,115$	$20$
$5,355$	$24$
$5,461$	$14,$ $28$
$6,141$	$22$
$6,223$	$21$
$6,235$	$28$
$6,355$	$20$
$6,765$	$20$
$6,951$	$30$
$7,161$	$30$
$7,735$	$24$
$8,191$	$13,$ $26$
$8,193$	$26$
$8,435$	$24$
$8,525$	$20$
$9,399$	$24$
$9,513$	$30$
$9,709$	$18$
$9,831$	$28$
$9,945$	$24$
$10,261$	$30$
$10,845$	$24$
$10,923$	$30$
$11,049$	$28$
$11,275$	$20$
$11,627$	$30$
$12,291$	$24$
$12,483$	$18$
$13,107$	$16,$ $32$
$13,797$	$18$
$13,923$	$24$
$13,981$	$20$
$14,043$	$30$
$14,351$	$28$
$14,577$	$28$
$14,949$	$30$
$15,183$	$24$
$15,665$	$24$
$15,709$	$22$
$16,383$	$14,$ $28$
$16,385$	$28$
$16,513$	$21$
$18,415$	$28$
$18,631$	$25$
$18,705$	$28$
$19,065$	$20$
$20,485$	$24$
$20,853$	$30$
$21,483$	$30$
$21,845$	$16,$ $32$
$21,931$	$24$
$23,205$	$24$
$24,295$	$28$
$24,573$	$26$
$25,305$	$24$
$25,487$	$30$
$25,575$	$20$
$27,305$	$28$
$28,197$	$24$
$28,679$	$24$
$29,127$	$18$
$30,783$	$30$
$31,775$	$20$
$32,767$	$15,$ $30$
$32,769$	$30$
$33,825$	$20$
$34,881$	$30$
$36,873$	$24$
$37,449$	$18$
$41,943$	$20$
$42,129$	$30$
$42,799$	$21$
$43,053$	$28$
$46,995$	$24$
$47,127$	$22$
$49,155$	$28$
$49,981$	$30$
$51,491$	$30$
$53,261$	$24$
$55,245$	$28$
$55,831$	$25$
$60,787$	$22$
$61,455$	$24$
$65,535$	$16,$ $32$
$65,537$	$32$
$65,793$	$24$
$69,615$	$24$
$69,905$	$20$
$71,755$	$28$
$71,827$	$30$
$72,885$	$28$
$75,915$	$24$
$76,461$	$30$
$81,915$	$28$
$86,037$	$24$
$87,381$	$18$
$92,349$	$30$
$95,325$	$20$
$98,301$	$30$
$104,643$	$30$
$109,655$	$24$
$112,871$	$30$
$131,071$	$17$
$140,911$	$28$
$140,985$	$24$
$143,395$	$24$
$149,943$	$30$
$154,473$	$30$
$158,369$	$28$
$159,783$	$24$
$178,481$	$23$
$182,361$	$22$
$184,365$	$24$
$196,611$	$32$
$197,379$	$24$
$209,715$	$20$
$215,265$	$28$
$215,481$	$30$
$229,383$	$30$
$256,999$	$29$
$258,111$	$24$
$262,143$	$18$
$262,657$	$27$
$266,305$	$24$
$294,903$	$30$
$299,593$	$21$
$327,685$	$32$
$328,965$	$24$
$338,613$	$30$
$349,525$	$20$
$349,867$	$30$
$360,437$	$30$
$372,827$	$24$
$416,179$	$28$
$422,733$	$28$
$430,185$	$24$
$449,829$	$30$
$463,419$	$30$
$475,107$	$28$
$479,349$	$24$
$486,737$	$29$
$524,287$	$19$
$549,791$	$30$
$617,093$	$28$
$646,443$	$30$
$704,555$	$28$
$790,097$	$30$
$791,845$	$28$
$798,915$	$24$
$983,055$	$32$
$986,895$	$24$
$1,015,839$	$30$
$1,048,575$	$20$
$1,049,601$	$30$
$1,081,311$	$30$
$1,082,401$	$25$
$1,114,129$	$32$
$1,118,481$	$24$
$1,248,537$	$28$
$1,290,555$	$24$
$1,398,101$	$22$
$1,549,411$	$30$
$1,649,373$	$30$
$1,838,599$	$27$
$1,851,279$	$28$
$1,864,135$	$24$
$2,080,895$	$28$
$2,097,151$	$21$
$2,113,665$	$28$
$2,304,167$	$29$
$2,370,291$	$30$
$2,375,535$	$28$
$2,396,745$	$24$
$3,085,465$	$28$
$3,148,803$	$30$
$3,243,933$	$30$
$3,342,387$	$32$
$3,355,443$	$24$
$3,848,537$	$30$
$4,194,303$	$22$
$4,648,233$	$30$
$4,948,119$	$30$
$5,570,645$	$32$
$5,592,405$	$24$
$6,242,685$	$28$
$7,110,873$	$30$
$8,388,607$	$23$
$9,256,395$	$28$
$10,845,877$	$30$
$11,545,611$	$30$
$13,944,699$	$30$
$16,711,935$	$32$
$16,777,215$	$24$
$16,843,009$	$32$
$17,043,521$	$30$
$17,895,697$	$28$
$19,173,961$	$27$
$22,369,621$	$26$
$32,537,631$	$30$
$33,554,431$	$25$
$34,636,833$	$30$
$50,529,027$	$32$
$51,130,563$	$30$
$53,687,091$	$28$
$67,108,863$	$26$
$84,215,045$	$32$
$89,478,485$	$28$
$97,612,893$	$30$
$119,304,647$	$30$
$134,217,727$	$27$
$153,391,689$	$30$
$252,645,135$	$32$
$268,435,455$	$28$
$286,331,153$	$32$
$357,913,941$	$30$
$536,870,911$	$29$
$858,993,459$	$32$
$1,073,741,823$	$30$
$1,431,655,765$	$32$
$2,147,483,647$	$31$