倍数判別

何か見たので。(数学ってほど数学してませんが)

予備

まず、
$(x + y)\mod z\equiv x\mod z+y\mod z$
したがって
$(\sum_{n=0}a_n)\mod z\equiv\sum_{n=0}{(a_n\mod z)}$、
$xy\mod z\equiv x\mod z\times y\mod z$
すなわち
$x^n\mod z=(x\mod z)^n$
である(証明抜きですみません)ことを念頭に置きます。

被判定数を$N=\sum_{n=0} 10^n a_n$と書きます。

2の倍数

下一桁が2の倍数(偶数)

$10\equiv 0\pmod 2$なので

3の倍数

すべての桁の数字を足して3で割れれば

$10\equiv 1\pmod 3$ゆえ、$\sum_{n=0}10^na_n\equiv\sum_{n=0}a_n\pmod 3$

4の倍数

下2桁が4の倍数

$100\equiv 0\pmod 4$なので

十の位が奇数のとき、一の位が$2, 6$
十の位が偶数のとき、一の位が$0, 4, 8$

$10\mod 4=2、20\mod 4=0$によります

5の倍数

下1桁が$0, 5$

$10\equiv 0\pmod 5$なので

6の倍数

2の倍数と3の倍数を両判定

$2\times 3=6$なので

7の倍数

十以上の桁を10で割ったもの(右シフト)から下1桁の2倍を引いて7の倍数であれば

これは$N=10n+a_0$と書いたとき$n-2a_0\equiv 0\pmod 7$であれば、という意味であります。

$(n-2a_0)\times 10=10n-20a_0$
ですが、
$-20\equiv 1\pmod 7$
なので
$a_0\equiv -20a_0\pmod 7$が成り立ちます。したがって
$n-2a_0\equiv 10n+a_0\pmod 7$

10以上の桁を10で割ったもの(右シフト)に下1桁の5倍を足して7の倍数であれば

($N=10n+a_0$のとき$n+5a_0$を判定に使う)でもいけます(証明略)。

桁数が多いとあまり役立たないように見えますが、繰り返し適用するという手があります。

下から3桁ずつに区切って、下3桁は足す-そのうえの3桁は引く-そのうえの3桁は足す、とやっていった数が7の倍数であれば
例: 123452のとき、-123+452=329が7の倍数なので123452もそう

$1000\equiv -1\pmod 7$
なので、
$\sum_{n=0}1000^n p_n=\sum_{n=0}(-1)^np_n\pmod 7$
これに、$p_n$は3ケタごとにバラした値としてやればよいわけです。

この判定方法は、$1000\equiv -1\pmod{11}$、$1000\equiv -1\pmod{13}$でもあるので、11または13でも使えるというのがユニークです。

8の倍数

下3桁が8の倍数

$1000\equiv 0\pmod 8$なので
場合分けが多くなりますが4の倍数のようなこともできます。

2桁以下の場合、以下のケースが8の倍数。

• 十の位が0、4、8のとき1の位は0、8 (4のときは4余り)
• 十の位が1、5、9のとき1の位は6 (2の時は4余り)
• 十の位が2、6のとき1の位は4 (0、8の時は4余り)
• 十の位が3、7のとき1の位は2 (6のときは4余り)

3桁のとき

• 百の位が偶数ならば、下位2桁が8で割り切れる場合
• 百の位が奇数ならば、下位2桁が8で割って4余る場合

2桁の場合は$x+y\mod 8\equiv x\mod 8+y\mod 8$であり、$10\mod 8=2、20\mod 8=4、30\mod 8=6$との組み合わせでどうにかなる形です。3桁はこれに$100\mod 8=4$が加わります。

9の倍数

すべての桁の数字を足して9で割れれば

$10\equiv 1\pmod 9$
ゆえ、
$\sum_{n=0}10^na_n\equiv\sum_{n=0}a_n\pmod 9$

10の倍数

下1桁が0

$10\equiv 0\pmod {10}$なので

11の倍数

下から奇数桁の数字の和から、下から偶数桁の数字の和を引いたものが11の倍数であれば

$10\equiv-1\pmod {11}$
により
$\sum_{n=0}10^n a_n=\sum_{n=0}(-1)^na_n\pmod {11}$

12の倍数

3と4の倍数の両判定

$12=3\times4$ですので

13の倍数

下から3桁ずつに区切って、下3桁は足す-そのうえの3桁は引く-そのうえの3桁は足す、とやっていった数が13の倍数であれば
例: 123422のとき、-123+422=299が13の倍数なので123422もそう

証明は7の倍数の2番目を参照。

小さいときには以下の判定も使えます。

十以上の桁を10で割ったもの(右シフト)と下1桁の4倍を足したものが13の倍数であれば

$N=10n+a_0$と書いたとき$n+4a_0\pmod{13}\equiv 0$ならば、という意味であります。
$(n+4a_0)\times 10=10n+40a_0$ですが、$40\equiv 1\pmod{13}$ですので
$10n+40a_0\equiv 10n+a_0\pmod{13}$
という次第です。

14の倍数

2と7の両判定

$14=2\times 7$なので

15の倍数

3と5の両判定

$15=3\times 5$ですね

16の倍数

これは大変。

下4桁が16の倍数

$10000\equiv 0\pmod{16}$だからですが、下4桁はあまり実用的とは言えません。これは4回2で割ってみるほうがよさそう。

17の倍数

下から2桁ずつに区切って、下2桁は足す-そのうえの2桁の2倍を引く-そのうえの2桁の4倍を足す、とやっていった数が17の倍数であれば

$100\equiv-2\pmod {17}$なので
$\sum_{n=0}100^n p_n\equiv\sum_{n=0}(-2)^np_n\pmod {17}$
ということなのですがあんまりエレガントでないですね

十以上の桁を10で割ったもの(右シフト)から下1桁の5倍をひいたものが17の倍数であれば

$N=10n+a_0$と書いたとき$n-5a_0\pmod{17}\equiv 0$ならば、という意味であります。
$(n-5a_0)\times 10=10n-50a_0$ですが、$50\equiv -1\pmod{13}$ですので
$10n-50a_0\equiv 10n+a_0\pmod{17}$ (符号反転に注意)
という次第です。

百以上の桁を100で割ったもの(右シフト)の2倍から下2桁をひいたものが17の倍数であれば

$N=100n+a_{10}$と書いたとき$2n-a_{10}\equiv 0\pmod{17}$ならば、という意味であります。
$N+(2n-a_{10}) = 102n\equiv 0\pmod{17}$ですから、$2n-a_{10}\equiv 0\pmod{17}$ならば$N\equiv 0\pmod{17}$ということですね。

18の倍数

2と9の倍数の両判定

$18=2\times 9$ですので

19の倍数

十以上の桁を10で割ったもの(右シフト)に下1桁の2倍を足したものが19の倍数であれば

$N=10n+a_0$と書いたとき$n+2a_0\pmod{19}\equiv 0$ならば、という意味であります。
$(n+2a_0)\times 10=10n+20a_0$ですが、$20\equiv 1\pmod{19}$ですので
$10n+20a_0\equiv 10n+a_0\pmod{19}$
という次第です。

被判定数を20で割った商と剰余を足して19の倍数になれば

$N=20n+p$とすると、$20n+p\equiv n+p\pmod{19}$というわけです。エレガントとは言えません。

20の倍数

4と5の倍数の両判定
ただしだいぶ簡単で、下2桁が$00, 20, 40, 60, 80$と列挙できます

$20=4\times 5$だからですが、ここまで簡単になる原因は4の倍数のところを参照。

21の倍数

3と7の両判定

$21=3\times 7$ですので

22の倍数

2と11の両判定

$22=2\times 11$ですので

23の倍数

十以上の桁を10で割ったもの(右シフト)と下1桁の7倍を足したものが23の倍数であれば

$N=10n+a_0$と書いたとき$n+7a_0\pmod{23}\equiv 0$ならば、という意味であります。
$(n+7a_0)\times 10=10n+70a_0$ですが、$70\equiv 1\pmod{23}$ですので
$10n+70a_0\equiv 10n+a_0\pmod{23}$
という次第です。

適用できる条件が厳しいですが

十以上の桁を10で割ったもの(右シフト)を下1桁の数字で割ったとき値が16であれば

$N=10n+a_0 (a_0\neq 0)$のとき$n/a_0=16$
ならば
$n=16a_0$、また$161\equiv 0\pmod{23}$
ですから
$N=161a_0\equiv 0\pmod {23}$て天下りな作戦ですね。

定数は、16でなくても23で割ってあまりが16であれば良いです

24の倍数

3と8の両判定

$24=3\times 8$ですので。4と6ではダメすよ(GCDが1にならない)

25の倍数

下2桁が00, 25, 50, 75

$100\equiv 0\pmod {25}$ですので下2桁だけでよいのはすぐにわかります。列挙するほどしかないのは偶然かと。

26の倍数

2と13の両判定

$26=2\times 13$なので

27の倍数

下から3桁ずつ区切って足していった和が27の倍数であれば

$1000\equiv 1\pmod{27}$
なので、
$\sum_{n=0}{1000^n}{p^n}\equiv\sum_{n=0}{p^n}\pmod {27}$
というわけです。小さい値の場合、9の倍数でフィルタすると速そうですね

十以上の桁を10で割ったもの(右シフト)から下1桁の8倍をひいたものが27の倍数であれば

$N=10n+a_0$と書いたとき$n-8a_0\pmod{27}\equiv 0$ならば、という意味であります。
$(n-8a_0)\times 10=10n-80a_0$ですが、$80\equiv -1\pmod{27}$ですので
$10n-80a_0\equiv 10n+a_0\pmod{27}$ (符号反転に注意)
という次第です。

28の倍数

4と7の両判定

$28=4\times 7$ですので

29の倍数

十以上の桁を10で割ったもの(右シフト)と下1桁の3倍を足したものが29の倍数であれば

$N=10n+a_0$と書いたとき$n+3a_0\pmod{29}\equiv 0$ならば、という意味であります。
$(n+3a_0)\times 10=10n+30a_0$ですが、$30\equiv 1\pmod{29}$ですので
$10n+30a_0\equiv 10n+a_0\pmod{29}$
という次第です。