29 の倍数判定法 - tsujimotterのノートブック

こんにちは。最近数学をする時間がとれなくてもやっとしているtsujimotterです*1。ちょっとした気晴らしに小ネタを書きたいと思います。

みなさんは，普段 29 の倍数をどのように判定していますか？

え？29 の倍数なんて，判定する機会なんてない？

普通そうですよね。でも，できたら楽しそうだと思いませんか。

twitter でそんな話をしていたら，とある方からこんな方法を教えてもらいました。

29の倍数判定、下一桁の3倍を残りに足したもので行けそうじゃないですか！？
58→5+24=29
2186629→218689→21895→2204→232→29
とか
— s(数学)k(くそほど)d(できない) (@ForgetMeNot9339) 2016年8月30日

面白そうですね！でも，どうしてこんな方法が成り立つのでしょうか。

$2186629$ という数が与えられたとき，その数の１桁目（この場合は $9$ ）に $3$ をかけ，２桁目以上の数（この場合は， $218662$ ）に加えます。すると，

$218662 + 3\times 9 = 218689$

が得られます。先ほどの判定法によると，この $218689$ が $29$ の倍数であれば，元の数 $2186629$ も $29$ の倍数です。そうでなければ，元の数は $29$ の倍数ではない。

つまり， $29$ の倍数の判定法を「桁を減らして」実行する事が可能なのです。

さらに言えば，この操作は繰り返すことができて，最終的に $29$ 以下の数に落とすことができます。結果が $29$ または $0$ であれば $29$ の倍数，そうでなければ $29$ の倍数ではない。こうして，簡単に（暗算でも） $29$ の倍数判定ができるというのです。すごいですね！

少し一般化して説明します。

ある数が $29$ の倍数であるかどうかを判定したいとします。その数の２桁目以上の数を $A$ とおき，１桁目の数を $b$ とおきます。すると，元の数は

$10A + b$

という式でかけるでしょう。

そして，この数が $29$ の倍数であるかどうかは，１桁目の数 $b$ に $3$ をかけたものに $A$ を加えた数，すなわち

$A + 3b$

が $29$ の倍数かどうかで判定ができるというのです。

このように数式で書いたところで，なんでこんなことがいえるのか訳がわかりませんね。

どうやっても，

$10A + b \equiv A + 3b \pmod{29} \tag{1}$
注：この式は間違っています。

の合同式を示す事ができません。法 $29$ において，両者のあまりが一致するようには到底思えないのです。あまりが一致しなければ，こんな式変形をしたところで， $29$ の倍数の判定ができないじゃないか。

結構悩みました。どうやったらこんな合同式を示せるのだろうと。

しばらく考えた結果，一つの考えに達しました。

別にあまりが一致しなくても良いじゃないか！

実は，示すべき結論が間違っていたのです。

本当に示すべきは，

$10A + b$ が $29$ の倍数 $\Longleftrightarrow$ $ A + 3b$ が $29$ の倍数 $\tag{2}$

だったのです。

２つの式は，似ているようでまったく異なります。

私はてっきり，元の数を $29$ で割ってあまりを持つとき，そのあまりは変形した数を $29$ で割ったあまりと等しいはずだ，と考えていました。でも，別にそうでなくてもよかったのです。

単に，左辺が $29$ の倍数のときに，右辺が $29$ の倍数であって，逆に右辺が $29$ の倍数のときに，左辺が $29$ の倍数であればよいのです。

どうしてこんな簡単なことに気づかなかったのでしょう。思い込みって恐ろしいですね。

これがわかれば，あとは簡単です。一気に証明してしまいましょう。

証明

$(10A+b)$ に $3$ をかけたものから $A+3b$ を引くと，以下が成り立つ．

$3(10A+b) - (A+3b) = 30A + 3b – A – 3b = 29A$

よって， $29$ で割ったあまりを考えると，

$3(10A+b) \equiv (A+3b) \pmod{29}$

が成り立ちます．

ここでもし，

$(10A+b) \equiv 0 \pmod{29}$

であれば

$A+3b \equiv 0 \pmod{29}$

が成り立ちます．

逆に，

$A+3b \equiv 0 \pmod{29}$

であれば，

$3(10A+b) \equiv 0 \pmod{29}$

となるわけですが，この両辺に $\bmod{29}$ における $3$ の逆元 $10$ をかけて*2

$10A + b \equiv 0 \pmod{29}$

となって $10A + b$ も $29$ の倍数になります．

以上より，

$10A + b$ が $29$ の倍数 $\Longleftrightarrow$ $A + 3b$ が $29$ の倍数

が示せました．

一般化

以上でめでたく $29$ の倍数の問題は解決したわけですが，実は今回の話はもっと一般化することができます。

今回のポイントは， $\bmod{29}$ における $10$ の逆元を使う，ということでした。

一般に素数 $p\neq 2, 5$ を法とした $10$ の逆元を $c_p$ としたとき，

$10A + b$ が $p$ の倍数 $\Longleftrightarrow$ $A + c_p b$ が $p$ の倍数 $\tag{2'}$

が成り立ちます。証明は先ほどとまったく同じです。

$p < 100$ における，逆元 $c_p$ を考えてみると，以下のようになります。

#p, c_p
3, 1
7, 5
11, 10
13, 4
17, 12
19, 2
23, 7
29, 3
31, 28
37, 26
41, 37
43, 13
47, 33
53, 16
59, 6
61, 55
67, 47
71, 64
73, 22
79, 8
83, 25
89, 9
97, 68

たとえば， $p = 19$ の場合は， $c_p = 2$ （すなわち， $10\cdot 2 \equiv 1 \pmod{19}$ ）を用いて，

$10A + b$ が $19$ の倍数 $\Longleftrightarrow$ $A + 2b$ が $19$ の倍数

が成り立ちます。

たとえば， $19$ の倍数である $65550$ は，

$\begin{align}65550 &\to 6555 \\ &\to 665 \\ &\to 76 \\ &\to 19 \end{align}$

となり，一瞬で $19$ の倍数であることがわかります。

ちなみに， $c_p$ の値が大きいときは， $c_p - p$ としても問題ありません。たとえば， $p = 7$ のとき， $c_p = 5$ ですが， $5$ 倍し続けるのは嫌ですよね。そんなときは， $c_p - p = 5- 7 =2$ として，

$10A + b$ が $7$ の倍数 $\Longleftrightarrow$ $A - 2b$ が $7$ の倍数

としてもいいわけです。実際，この判定法は $7$ の倍数法として比較的よく知られているようです。

おわりに

いやぁ，面白いですね。まさか $29$ の倍数判定法に，こんな簡便なものがあるとは思いませんでした。

倍数の判定法は，なかなか奥が深いのでぜひみなさんも考えてみてください。

私自身は，倍数の判定なら「フェルマーの小定理」だろう，と思ってそればかり考えていたのですが・・・。中途半端な知識は，人を頭でっかちにさせることもあるのですね。気をつけないと。

フェルマーの小定理といえば「循環小数」関連の話題も面白いです。よかったらこちらもご覧になってください。
tsujimotter.hatenablog.com

最後に，もう一つ重要な事実を指摘しておきたいと思います。

この判定法を教えてくれた方は「s(数学)k(くそほど)d(できない) 」というスクリーンネームの方なのですが・・・

十分，数学できるじゃないか！！

数学できる人ほどこういうことを言うんですよね。なんつって笑
（教えてくださってありがとうございます ^_^）

それでは，今日はこの辺で！

*1:「数学する時間がとれない」というより「数学はしているけど，ブログを書いている暇がない」かもしれません。今，書きたいブログ記事が６個くらい溜まっています。

*2:逆元というのは，かけると $1$ になるような数のこと．たとえば，法 $29$ で $10$ に $3$ をかけると $10\cdot 3\equiv 1\pmod{29}$ より，法 $29$ において $3$ は $10$ の逆元．