倍数判定法を合同式で理解する
倍数判定法を合同式で理解する
はじめに
生徒に質問されたので，$\LaTeX$のリハビリも兼ねて久々に記事を書いた．
説明の都合上，一貫して積の記号を省略しない．
例えば，$a_1a_2a_3(a_n=2\cdot n+1)$は$a_1a_2a_3=a_1\cdot a_2\cdot a_3=3\cdot5\cdot7=105$ではなく， $a_1a_2a_3=357$を意味する．
また，次に注意せよ．
$a,b,c,d,p(\neq0) \in \mathbb Z$ に対し，
$$
1. \ \ a \equiv b \pmod p\ , c \equiv d \pmod p \implies a + c\equiv b + d \pmod p
$$
$$
2. \ \ a \equiv b \pmod p\ , c \equiv d \pmod p \implies a \cdot c \equiv b \cdot d \pmod p
$$
$$
3. \ \ a \equiv b \pmod p \implies a^n \equiv b^n \pmod p \ (n \in \mathbb N^+)
$$
$1.$
あまりを元の数から引いたら$p$で割り切れる．(それを$p \mid \square$と書く．(読み：$p$ divides $\square$.))
$p \mid (a - b) \ , \ p \mid (c - d)$だから，
$\therefore a + c = (a - b) + (c - d) + b + d \equiv b+d \pmod p.$
$2.$
$p \mid (a - b) \ , \ p \mid (c - d)$より，$\ p \mid (a - b)\cdot c \ , \ p \mid (d - c)\cdot b$だから，
$\therefore a \cdot c
= (a - b) \cdot c +b \cdot c
\equiv b \cdot c + (d - c) \cdot b
\equiv b \cdot d \pmod p.$
$3.$
$2.$の$c,d$をそれぞれ$a,b$に置き換えて$n$回繰り返す．
以下，$A:=\cdots a_2a_1$とする．
$2^n,5^n$の倍数判定法
$2^n,5^n \mid A \iff 2^n,5^n \mid a_na_{n-1}\cdots a_1$
$10^n = 2^n \cdot 5^n$を利用する．
$k \geq n$なる$k$に対し,$10^k = 2^n \cdot 5^n \cdot 10^{k-n} \equiv0 \pmod {2^n,5^n}$より，$a \cdot 10^{k}\equiv0 \pmod {2^n,5^n}$だから，
$\therefore A=\cdots +a_{n+2}\overbrace{00 \cdots 0}^{(n+1)\mathrm個}+a_{n+1}\overbrace{00 \cdots 0}^{n\mathrm個}+a_na_{n-1} \cdots a_1 \equiv a_na_{n-1}\cdots a_1 \pmod {2^n,5^n}.$
解答
$3696504 \equiv 504(=400+104) \equiv 104(=80+24) \equiv 24 \equiv 0 \pmod8 $ $\ldots 8$の倍数.
$ 3,9$の倍数判定法
$10 \equiv 1 \pmod3 \ , \ 10 \equiv 1 \pmod9$を利用する．
$3,9 \mid A \iff 3,9 \mid (\cdots + a_2 + a_1)$
$10 \equiv 1 \pmod{3,9}$より,$a\cdot10^n \equiv a \pmod{3,9}$だから，
$\therefore A=\cdots + a_3 00 +a_2 0+a_1 \equiv \cdots +a_3 +a_2 +a_1 \pmod {3,9} .$
解答
$3696504 \equiv 3+6+9+6+5+0+4 $
$\equiv 5+4 \ (3\mathrm{の倍数を除いておくと計算しやすい}) \equiv 9 \equiv 0 \pmod3 $
$\ldots 3$の倍数.
$3696504 \equiv 3+6+9+6+5+0+4 $
$\equiv 3+6+6+5+4 \ (9\mathrm{の倍数を除いておくと計算しやすい}) \equiv 9+6+9 \equiv 6 \pmod9 $
$\ldots 9$の倍数ではない.
$7,11,13$の倍数判定法
$1001=7 \cdot 11 \cdot 13$を利用する．
面倒なので教えず，「実際に割って確かめろ」と指導する講師が多い．
余談だが，$1001$は千夜一夜物語にちなみ"シェヘラザード数"と呼ばれている．
$7,11,13 \mid A \iff 7,11,13 \mid (\cdots +(-1)^na_{3n+3}a_{3n+2}a_{3n+1}\cdots -a_6a_5a_4+a_3a_2a_1)$
要は$A$を$3$桁ごとに区切って足し引きする．
$A$が$p$の倍数なら，$A \equiv 0 \pmod p \iff -A \equiv 0 \pmod p$だから，倍数判定時は(後述する，剰余を求めるときはNG)符号が交互に代わってさえいれば逆でもよい．
$10^3 \equiv -1 \pmod{7,11,13}$より，$a\cdot10^{3n} \equiv a\cdot (-1)^n \pmod{7,11,13}$だから，
$$\begin{align}
\therefore
A & = \cdots + a_{3n+3}a_{3n+2}a_{3n+1}\overbrace{00 \cdots 0}^{3n\mathrm個} + \cdots + a_6a_5a_4 000 + a_3a_2a_1\\
& \equiv \cdots +(-1)^na_{3n+3}a_{3n+2}a_{3n+1} + \cdots -a_6a_5a_4+a_3a_2a_1\pmod{7,11,13}.
\end{align}$$
解答
$94248 \equiv - 094 + 248 \equiv 154 \equiv 2 \cdot 7 \cdot 11 \pmod {7,11,13}$
$\ldots 7,11$の倍数．$13$の倍数ではない．
ん?
・倍数が$10^n+\alpha$となる整数の倍数判定法を自作できないか?
・倍数判定式とあまりは一致しないか?
ここまで読んでこのように思った者はちゃんと理解できていると思うので，これ以降も読むとよい．
$7$の倍数判定法2
先ほど3桁まで絞った後，あとは丸投げされたと思っただろうが，そう落胆しないでほしい．
$1. \ \ 7 \mid abc \iff 7 \mid (2\cdot a+bc)$
$2. \ \ 7 \mid abc \iff 7 \mid (ab-2\cdot c)$
$1.$
$ 100 \equiv 2 \pmod7$ より，$\therefore abc = a00 + bc \equiv 2\cdot a+bc \pmod7.$
$2.$
$21 \equiv 0\pmod7 \ , \ 7\perp10$ より，$\therefore abc = ab0 - 20\cdot c +21\cdot c \equiv (ab-2 \cdot c)\cdot 10
\pmod7.$
これは中学受験対策などで結果だけ覚えさせられた者が多いだろう．
絶対に$100$を超えないから，俺は定理$4-2$が好きだ．
解答
$10 \equiv -1 \pmod {11}$より，$a \cdot 10^n \equiv a\cdot (-1)^n \pmod {11}$だから，
$A=\cdots + a_3 00 +a_2 0+a_1 \equiv \cdots +a_3 -a_2 +a_1 \pmod {11}$
$\therefore 11 \mid A \iff 11 \mid (\cdots +(-1)^{n-1}a_n + \cdots -a_2 + a_1)$
※簡単だから，参考書にはこちらが載っているのをよく見かける．
解答
$37 \cdot 3 \cdot 9 = 111 \cdot 9 = 999$より，$1000 \equiv 1 \pmod {37}$だから，$a \cdot 10^{3n} \equiv a \pmod {37}$
$$\begin{align}
A & = \cdots + a_{3n+3}a_{3n+2}a_{3n+1}\overbrace{00 \cdots 0}^{3n\mathrm個} + \cdots + a_6a_5a_4 000 + a_3a_2a_1\\
& \equiv \cdots + a_{3n+3}a_{3n+2}a_{3n+1} + \cdots + a_6a_5a_4+a_3a_2a_1 \pmod{37}.
\end{align}$$
$\therefore 37 \mid A \iff 37 \mid (\cdots + a_{3n+3}a_{3n+2}a_{3n+1}\cdots +a_6a_5a_4+a_3a_2a_1)$
($3$桁ごとに区切って足すという操作を繰り返して作った$3$桁の数が$37$の倍数ならば$A$も$37$の倍数)
解答
$6$進法において，
$10 \equiv 1 \pmod {5}$だから，$a \cdot 10^{n} \equiv a \pmod {5}$
$A = \cdots + a_3 00 +a_2 0+a_1 \equiv \cdots +a_3 +a_2 +a_1 \pmod {5} .$
$\therefore 5 \mid A \iff 5 \mid (\cdots + a_2 + a_1)$
$9$の倍数判定時に気付いた者もいると思うが，$n$進法において$10 - 1 = n - 1$だから，$n - 1$の倍数判定法は須らく，桁の和が$n - 1$の倍数かどうかになる．
割り勘
定理$4-2$以外のような，倍数が$10^n+\alpha$型のものは見てわかる通り，あまりと判定法が一致している．
これを俺はカラオケや飲み会などで割り勘をする際の小テクとして用いている．
解答
$8254 \equiv 8+2+5+4 \equiv 1 \pmod3$だから，
$$\therefore \frac{8254-1}3 = \frac{9000-750+3}3 = 2751.$$
実際に割り勘するとき，簡単のため，$8254 = 8100 + 154 \equiv 154 \pmod3$(聖人) や，$8254 = 8400 - 146 \equiv -146 \pmod3$(邪悪)としても良いだろう．
最後に
人生で一番\cdotを打った気がする．
使用例は
これ
等を参照せよ．