倍数判定法を合同式で理解する

109

倍数判定法を合同式で理解する

はじめに

生徒に質問されたので， $L A T E X$ のリハビリも兼ねて久々に記事を書いた．

説明の都合上，一貫して積の記号を省略しない．
例えば， $a_{1} a_{2} a_{3} (a_{n} = 2 \cdot n + 1)$ は $a_{1} a_{2} a_{3} = a_{1} \cdot a_{2} \cdot a_{3} = 3 \cdot 5 \cdot 7 = 105$ ではなく， $a_{1} a_{2} a_{3} = 357$ を意味する．

また，次に注意せよ．

合同式の性質

$a, b, c, d, p (\neq 0) \in Z$ に対し，
$1. a \equiv b (\mod p), c \equiv d (\mod p) ⟹ a + c \equiv b + d (\mod p)$
$2. a \equiv b (\mod p), c \equiv d (\mod p) ⟹ a \cdot c \equiv b \cdot d (\mod p)$
$3. a \equiv b (\mod p) ⟹ a^{n} \equiv b^{n} (\mod p) (n \in N^{+})$

$1.$
あまりを元の数から引いたら $p$ で割り切れる．(それを $p ∣ ◻$ と書く．(読み： $p$ divides $◻$ .))
$p ∣ (a - b), p ∣ (c - d)$ だから，
$∴ a + c = (a - b) + (c - d) + b + d \equiv b + d (\mod p) .$

$2.$
$p ∣ (a - b), p ∣ (c - d)$ より， $p ∣ (a - b) \cdot c, p ∣ (d - c) \cdot b$ だから，
$∴ a \cdot c = (a - b) \cdot c + b \cdot c \equiv b \cdot c + (d - c) \cdot b \equiv b \cdot d (\mod p) .$

$3.$
$2.$ の $c, d$ をそれぞれ $a, b$ に置き換えて $n$ 回繰り返す．

以下， $A := \dots a_{2} a_{1}$ とする．

$2^{n}, 5^{n}$ の倍数判定法

2^{n}, 5^{n}

の倍数判定法

$2^{n}, 5^{n} ∣ A ⟺ 2^{n}, 5^{n} ∣ a_{n} a_{n - 1} \dots a_{1}$

$10^{n} = 2^{n} \cdot 5^{n}$ を利用する．

$k \geq n$ なる $k$ に対し, $10^{k} = 2^{n} \cdot 5^{n} \cdot 10^{k - n} \equiv 0 (\mod 2^{n}, 5^{n})$ より， $a \cdot 10^{k} \equiv 0 (\mod 2^{n}, 5^{n})$ だから，

$∴ A = \dots + a_{n + 2} \overset{(n + 1) 個}{\overset{⏞}{00 \dots 0}} + a_{n + 1} \overset{n 個}{\overset{⏞}{00 \dots 0}} + a_{n} a_{n - 1} \dots a_{1} \equiv a_{n} a_{n - 1} \dots a_{1} (\mod 2^{n}, 5^{n}) .$

3696504

は

8

の倍数か?

解答

$3696504 \equiv 504 (= 400 + 104) \equiv 104 (= 80 + 24) \equiv 24 \equiv 0 (\mod 8)$ $\dots 8$ の倍数.

$3, 9$ の倍数判定法

$10 \equiv 1 (\mod 3), 10 \equiv 1 (\mod 9)$ を利用する．

3, 9

の倍数判定法

$3, 9 ∣ A ⟺ 3, 9 ∣ (\dots + a_{2} + a_{1})$

$10 \equiv 1 (\mod 3, 9)$ より, $a \cdot 10^{n} \equiv a (\mod 3, 9)$ だから，

$∴ A = \dots + a_{3} 00 + a_{2} 0 + a_{1} \equiv \dots + a_{3} + a_{2} + a_{1} (\mod 3, 9) .$

3696504

は

3, 9

の倍数か?

解答

$3696504 \equiv 3 + 6 + 9 + 6 + 5 + 0 + 4$
$\equiv 5 + 4 (3 の倍数を除いておくと計算しやすい) \equiv 9 \equiv 0 (\mod 3)$
$\dots 3$ の倍数.

$3696504 \equiv 3 + 6 + 9 + 6 + 5 + 0 + 4$
$\equiv 3 + 6 + 6 + 5 + 4 (9 の倍数を除いておくと計算しやすい) \equiv 9 + 6 + 9 \equiv 6 (\mod 9)$
$\dots 9$ の倍数ではない.

$7, 11, 13$ の倍数判定法

$1001 = 7 \cdot 11 \cdot 13$ を利用する．
面倒なので教えず，「実際に割って確かめろ」と指導する講師が多い．
余談だが， $1001$ は千夜一夜物語にちなみ"シェヘラザード数"と呼ばれている．

7, 11, 13

の倍数判定法

$7, 11, 13 ∣ A ⟺ 7, 11, 13 ∣ (\dots + (- 1)^{n} a_{3 n + 3} a_{3 n + 2} a_{3 n + 1} \dots - a_{6} a_{5} a_{4} + a_{3} a_{2} a_{1})$

要は $A$ を $3$ 桁ごとに区切って足し引きする．
$A$ が $p$ の倍数なら， $A \equiv 0 (\mod p) ⟺ - A \equiv 0 (\mod p)$ だから，倍数判定時は(後述する，剰余を求めるときはNG)符号が交互に代わってさえいれば逆でもよい．

$10^{3} \equiv - 1 (\mod 7, 11, 13)$ より， $a \cdot 10^{3 n} \equiv a \cdot (- 1)^{n} (\mod 7, 11, 13)$ だから，
$\begin{aligned} ∴ A & = \dots + a_{3 n + 3} a_{3 n + 2} a_{3 n + 1} \overset{3 n 個}{\overset{⏞}{00 \dots 0}} + \dots + a_{6} a_{5} a_{4} 000 + a_{3} a_{2} a_{1} \\ \equiv \dots + (- 1)^{n} a_{3 n + 3} a_{3 n + 2} a_{3 n + 1} + \dots - a_{6} a_{5} a_{4} + a_{3} a_{2} a_{1} (\mod 7, 11, 13) . \end{aligned}$

94248

は

7, 11, 13

の倍数か?

解答

$94248 \equiv - 094 + 248 \equiv 154 \equiv 2 \cdot 7 \cdot 11 (\mod 7, 11, 13)$
$\dots 7, 11$ の倍数． $13$ の倍数ではない．

ん?

・倍数が $10^{n} + α$ となる整数の倍数判定法を自作できないか?
・倍数判定式とあまりは一致しないか?

ここまで読んでこのように思った者はちゃんと理解できていると思うので，これ以降も読むとよい．

$7$ の倍数判定法2

先ほど3桁まで絞った後，あとは丸投げされたと思っただろうが，そう落胆しないでほしい．

7

の倍数判定法2

$1. 7 ∣ a b c ⟺ 7 ∣ (2 \cdot a + b c)$
$2. 7 ∣ a b c ⟺ 7 ∣ (a b - 2 \cdot c)$

$1.$
$100 \equiv 2 (\mod 7)$ より， $∴ a b c = a 00 + b c \equiv 2 \cdot a + b c (\mod 7) .$

$2.$
$21 \equiv 0 (\mod 7), 7 ⊥ 10$ より， $∴ a b c = a b 0 - 20 \cdot c + 21 \cdot c \equiv (a b - 2 \cdot c) \cdot 10 (\mod 7) .$

これは中学受験対策などで結果だけ覚えさせられた者が多いだろう．
絶対に $100$ を超えないから，俺は定理 $4 - 2$ が好きだ．

他の

11

の倍数判定法を作れ．

解答

$10 \equiv - 1 (\mod 11)$ より， $a \cdot 10^{n} \equiv a \cdot (- 1)^{n} (\mod 11)$ だから，
$A = \dots + a_{3} 00 + a_{2} 0 + a_{1} \equiv \dots + a_{3} - a_{2} + a_{1} (\mod 11)$

$∴ 11 ∣ A ⟺ 11 ∣ (\dots + (- 1)^{n - 1} a_{n} + \dots - a_{2} + a_{1})$

※簡単だから，参考書にはこちらが載っているのをよく見かける．

37

の倍数判定法を作れ．

解答

$37 \cdot 3 \cdot 9 = 111 \cdot 9 = 999$ より， $1000 \equiv 1 (\mod 37)$ だから， $a \cdot 10^{3 n} \equiv a (\mod 37)$

$\begin{aligned} A & = \dots + a_{3 n + 3} a_{3 n + 2} a_{3 n + 1} \overset{3 n 個}{\overset{⏞}{00 \dots 0}} + \dots + a_{6} a_{5} a_{4} 000 + a_{3} a_{2} a_{1} \\ \equiv \dots + a_{3 n + 3} a_{3 n + 2} a_{3 n + 1} + \dots + a_{6} a_{5} a_{4} + a_{3} a_{2} a_{1} (\mod 37) . \end{aligned}$

$∴ 37 ∣ A ⟺ 37 ∣ (\dots + a_{3 n + 3} a_{3 n + 2} a_{3 n + 1} \dots + a_{6} a_{5} a_{4} + a_{3} a_{2} a_{1})$
( $3$ 桁ごとに区切って足すという操作を繰り返して作った $3$ 桁の数が $37$ の倍数ならば $A$ も $37$ の倍数)

6

進法における

5

の倍数判定法を作れ．

解答

$6$ 進法において，
$10 \equiv 1 (\mod 5)$ だから， $a \cdot 10^{n} \equiv a (\mod 5)$

$A = \dots + a_{3} 00 + a_{2} 0 + a_{1} \equiv \dots + a_{3} + a_{2} + a_{1} (\mod 5) .$

$∴ 5 ∣ A ⟺ 5 ∣ (\dots + a_{2} + a_{1})$

$9$ の倍数判定時に気付いた者もいると思うが， $n$ 進法において $10 - 1 = n - 1$ だから， $n - 1$ の倍数判定法は須らく，桁の和が $n - 1$ の倍数かどうかになる．

割り勘

定理 $4 - 2$ 以外のような，倍数が $10^{n} + α$ 型のものは見てわかる通り，あまりと判定法が一致している．
これを俺はカラオケや飲み会などで割り勘をする際の小テクとして用いている．

8254

を

3

で割った数を超えない最大の整数を求めよ．

解答

$8254 \equiv 8 + 2 + 5 + 4 \equiv 1 (\mod 3)$ だから，
$∴ \frac{8254 - 1}{3} = \frac{9000 - 750 + 3}{3} = 2751.$

実際に割り勘するとき，簡単のため， $8254 = 8100 + 154 \equiv 154 (\mod 3)$ (聖人) や， $8254 = 8400 - 146 \equiv - 146 (\mod 3)$ (邪悪)としても良いだろう．

最後に

人生で一番\cdotを打った気がする．
使用例はこれ等を参照せよ．

投稿日：2024年5月28日

更新日：2024年9月1日

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

ドジコジ

6032

東北大学工学研究科出身できるだけ受け売りはせず，自分で思いついた解法や妄想を備忘録がてら書き綴っていこうと思います．

他の人のコメント

コメントはありません。

読み込み中

ドジコジ

倍数判定法を合同式で理解する

倍数判定法を合同式で理解する
はじめに
$2^{n}, 5^{n}$ の倍数判定法
$3, 9$ の倍数判定法
$7, 11, 13$ の倍数判定法
ん?
$7$ の倍数判定法2
割り勘
最後に

倍数判定法を合同式で理解する