読者です 読者をやめる 読者になる 読者になる

tsujimotterのノートブック

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

29 の倍数判定法

数学 整数論

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


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

え?29 の倍数なんて,判定する機会なんてない?

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

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


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

 2186629 という数が与えられたとき,その数の1桁目(この場合は  9)に  3 をかけ,2桁目以上の数(この場合は, 218662)に加えます。すると,

 218662 + 3\times 9 = 218689

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

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

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


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

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

 10A + b

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

そして,この数が  29 の倍数であるかどうかは,1桁目の数  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}

だったのです。

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:「数学する時間がとれない」というより「数学はしているけど,ブログを書いている暇がない」かもしれません。今,書きたいブログ記事が6個くらい溜まっています。

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