倍数判別

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

予備
--
まず、
$(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の倍数
--
:::note 
下一桁が2の倍数(偶数)
:::
$10\equiv 0\pmod 2$なので

3の倍数
--
:::note
すべての桁の数字を足して3で割れれば
:::
$10\equiv 1\pmod 3$ゆえ、$\sum_{n=0}10^na_n\equiv\sum_{n=0}a_n\pmod 3$

4の倍数
--
:::note
下2桁が4の倍数
:::
$100\equiv 0\pmod 4$なので

:::note
十の位が奇数のとき、一の位が$2, 6$
十の位が偶数のとき、一の位が$0, 4, 8$
:::
$10\mod 4=2、20\mod 4=0$によります

5の倍数
--
:::note
下1桁が$0, 5$
:::
$10\equiv 0\pmod 5$なので

6の倍数
--
:::note
2の倍数と3の倍数を両判定
:::
$2\times 3=6$なので

7の倍数
--
:::note
十以上の桁を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$

:::note
10以上の桁を10で割ったもの(右シフト)に下1桁の5倍を足して7の倍数であれば
:::
 ($N=10n+a_0$のとき$n+5a_0$を判定に使う)でもいけます(証明略)。

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


:::note
下から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の倍数
--
:::note
下3桁が8の倍数
:::
$1000\equiv 0\pmod 8$なので
場合分けが多くなりますが4の倍数のようなこともできます。

:::note
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の倍数
--
:::note
すべての桁の数字を足して9で割れれば
:::
$10\equiv 1\pmod 9$
ゆえ、
$\sum_{n=0}10^na_n\equiv\sum_{n=0}a_n\pmod 9$

10の倍数
--
:::note
下1桁が0
:::
$10\equiv 0\pmod {10}$なので

11の倍数
--
:::note
下から奇数桁の数字の和から、下から偶数桁の数字の和を引いたものが11の倍数であれば
:::
$10\equiv-1\pmod {11}$
により
$\sum_{n=0}10^n a_n=\sum_{n=0}(-1)^na_n\pmod {11}$

12の倍数
--
:::note
3と4の倍数の両判定
:::
$12=3\times4$ですので

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

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

:::note
十以上の桁を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の倍数
--
:::note
2と7の両判定
:::
$14=2\times 7$なので

15の倍数
--
:::note
3と5の両判定
:::
$15=3\times 5$ですね

16の倍数
--
これは大変。

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

17の倍数
---
:::note
下から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}$
ということなのですがあんまりエレガントでないですね

:::note
十以上の桁を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}$ (符号反転に注意)
という次第です。

:::note
百以上の桁を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の倍数
---
:::note
2と9の倍数の両判定
:::
$18=2\times 9$ですので

19の倍数
---
:::note
十以上の桁を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}$
という次第です。

:::note
被判定数を20で割った商と剰余を足して19の倍数になれば
:::
$N=20n+p$とすると、$20n+p\equiv n+p\pmod{19}$というわけです。エレガントとは言えません。

20の倍数
--
:::note
4と5の倍数の両判定
ただしだいぶ簡単で、下2桁が$00, 20, 40, 60, 80$と列挙できます
:::
$20=4\times 5$だからですが、ここまで簡単になる原因は4の倍数のところを参照。

21の倍数
--
:::note
3と7の両判定
:::
$21=3\times 7$ですので

22の倍数
--
:::note
2と11の両判定
:::
$22=2\times 11$ですので

23の倍数
--
:::note
十以上の桁を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}$
という次第です。

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

:::note
十以上の桁を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の倍数
--
:::note
3と8の両判定
:::
$24=3\times 8$ですので。4と6ではダメすよ(GCDが1にならない)

25の倍数
--
:::note
下2桁が00, 25, 50, 75
:::
$100\equiv 0\pmod {25}$ですので下2桁だけでよいのはすぐにわかります。列挙するほどしかないのは偶然かと。

26の倍数
--
:::note
2と13の両判定
:::
$26=2\times 13$なので

27の倍数
--
:::note
下から3桁ずつ区切って足していった和が27の倍数であれば
:::
$1000\equiv 1\pmod{27}$
なので、
$\sum_{n=0}{1000^n}{p^n}\equiv\sum_{n=0}{p^n}\pmod {27}$
というわけです。小さい値の場合、9の倍数でフィルタすると速そうですね

:::note
十以上の桁を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の倍数
--
:::note
4と7の両判定
:::
$28=4\times 7$ですので

29の倍数
--
:::note
十以上の桁を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}$
という次第です。