tsujimotterのノートブック

日曜数学者 tsujimotter の「趣味で数学」実践ノート

29 の倍数判定法

æ•°å­¦ æ•´æ•°è«–

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


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

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

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

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


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

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 の逆元．