和からの松中です。
先日こちらの記事で電卓を使って実数aのn乗根を求める方法について紹介しました。
しかしこの方法で任意の自然数nに対してaのn乗根を求めることができるわけではありません。記事の中で「nがあるメルセンヌ数の約数として現れること」がaのn乗根を求めることができるために重要であることを示しました。
正確に述べると、紹介した方法でaのn乗根を求めることができるnの必要十分条件は、「n=2l×m (mは奇数)と表したとき、mがメルセンヌ数の約数になる」ということになります。2l部分は『−−√』ボタンをl回押すことで実現できるため、奇数mがメルセンヌ数の約数に現れるかどうかだけが最大の関心事になります。
ここでメルセンヌ数とは2p−1の形をした自然数の事です。紛らわしいですがpは素数とは限らない自然数です。ある自然数がメルセンヌ数の約数に出てくるか否かはとても難しい問題のように思えたのですが、みうらさん(@miura_prime)から
「最後のほうの問い『任意の自然数がメルセンヌ数の約数になり得るのか?』について、（偶数はメルセンヌ数の約数になり得ないですが、）“任意の奇数はあるメルセンヌ数の約数になる”ことに気づいたのでご連絡しました。フェルマーの小定理の応用で示せます。」
とご連絡をいただきました(みうらさんコメント誠にありがとうございました。)。
少し考えてみると任意の奇数がメルセンヌ数の約数に現れることが、意外なほどあっさりわかってしまいました。つまり、ルートボタンがついた電卓を用いると、任意の自然数nについてaのn乗根を求めることができることが分かったのです。
メルセンヌ数の約数なんてとても難しそうということで考察をしなかった自分に反省し、本記事ではその証明を紹介し、いくつかの奇数に対しその奇数を約数にもつメルセンヌ数を具体的に求めてみます。
この記事の主な内容
メルセンヌ数の約数
まずはメルセンヌ数の約数にどのようなものが現れるか観察してみましょう。p=2,3,4,⋯,30としたときのメルセンヌ数と、その素因数を列挙してみます。
| p | 2p−1 | 素因数 |
|---|---|---|
| 2 | 3 | 3 |
| 3 | 7 | 7 |
| 4 | 15 | 3,5 |
| 5 | 31 | 31 |
| 6 | 63 | 3,3,7 |
| 7 | 127 | 127 |
| 8 | 255 | 3,5,17 |
| 9 | 511 | 7,73 |
| 10 | 1023 | 3,11,31 |
| 11 | 2047 | 23,89 |
| 12 | 4095 | 3,3,5,7,13 |
| 13 | 8191 | 8191 |
| 14 | 16383 | 3,43,127 |
| 15 | 32767 | 7,31,151 |
| 16 | 65535 | 3,5,17,257 |
| 17 | 131071 | 131071 |
| 18 | 262143 | 3,3,3,7,19,73 |
| 19 | 524287 | 524287 |
| 20 | 1048575 | 3,5,5,11,31,41 |
| 21 | 2097151 | 7,7,127,337 |
| 22 | 4194303 | 3,23,89,683 |
| 23 | 8388607 | 47,178481 |
| 24 | 16777215 | 3,3,5,7,13,17,241 |
| 25 | 33554431 | 31,601,1801 |
| 26 | 67108863 | 3,2731,8191 |
| 27 | 134217727 | 7,73,262657 |
| 28 | 268435455 | 3,5,29,43,113,127 |
| 29 | 536870911 | 233,1103,2089 |
| 30 | 1073741823 | 3,3,7,11,31,151,331 |
この表を見るとp=30までの範囲では37や53などの奇数がメルセンヌ数の約数として現れていないことが分かります。ちなみに、33も同様に現れていませんが、3と11を約数にもつメルセンヌ数210−1の約数になっていることは注意してください。
メルセンヌ数の約数は不規則のように見えます。この先37や53が登場するかどうかは何とも言えない気分になりますし、ましてや適当に与えた奇数(例えば397など)がこの先出てくるかどうかは全く予想できないように思えます。それが次の章で紹介するオイラーの定理を用いることでいとも簡単に示せてしまうのです。
オイラーの定理
オイラーは数学のあらゆる分野に業績を残す数学界の巨匠です。オイラーの○○公式、オイラーの○○定理、オイラー○○方程式、オイラー○○法などオイラーの名前が入った数学用語はたくさんあります。マスログでも過去に紹介しています。
さて、今回の証明で用いるのはオイラーが数論分野で残した「オイラーの定理」です。
オイラーの定理
aとmを互いに素な自然数とするときaφ(m)−1はmで割り切れる。
ここで、φはオイラーのトーシェント関数と呼ばれる関数で、自然数mに対して、φ(m)は1以上m以下の自然数でmと互いに素な自然数の個数を返します。例えば、1以上12以下の自然で12と互いに素なものは1,5,7,11の4個であるためφ(12)=4となります。
具体的な数でオイラーの定理が成り立つことを確認してみましょう。
例1
a=7、m=12とします。7と12の最大公約数は1、つまり7と12は互いに素であることからオイラーの定理の前提を満たします。先に示した通りφ(12)=4ですから、
aφ(m)−1=74−1=2401−1=2400
となり、2400=12⋅200より確かにaφ(m)−1はm=12で割り切れます。
例2
a=53、m=19とします。53と19はそれぞれ素数なので、当然互いに素です。素数pに対してφ(p)=p−1は容易に分かるため、φ(19)=18です。
よって、
aφ(m)−1=5318−1=10888439761782913818722623349689−1=10888439761782913818722623349688=19×573075776935942832564348597352
となり、確かにaφ(m)−1はm=19で割り切れます。
メルセンヌ数の約数について
本題に戻りましょう。任意の奇数mに対して、mと2は互いに素であるため、オイラーの定理から2φ(m)−1はmで割り切れることが分かります。2φ(m)−1はメルセンヌ数ですから、当初の目的である「任意の奇数があるメルセンヌ数の約数になる」ことが分かりました。とても簡単ですね。
実際にm=3,5,7,⋯31に対して、計算してみました。ここで前記事と合わせるために、p=φ(m)、q=(2p−1)/mも一緒に記載します。
| m | φ(m) | 2φ(m)−1 | p | q |
|---|---|---|---|---|
| 3 | 2 | 3=3×1 | 2 | 1 |
| 5 | 4 | 15=5×3 | 4 | 3 |
| 7 | 6 | 63=7×9 | 6 | 9 |
| 9 | 6 | 63=9×7 | 6 | 7 |
| 11 | 10 | 1023=11×93 | 10 | 93 |
| 13 | 12 | 4095=13×315 | 12 | 315 |
| 15 | 8 | 255=15×17 | 8 | 17 |
| 17 | 16 | 65535=17×3855 | 16 | 3855 |
| 19 | 18 | 262143=19×13797 | 18 | 13797 |
| 21 | 12 | 4095=21×195 | 12 | 195 |
| 23 | 22 | 4194303=23×182361 | 22 | 182361 |
| 25 | 20 | 1048575=25×41943 | 20 | 41943 |
| 27 | 18 | 262143=27×9709 | 18 | 9709 |
| 29 | 28 | 268435455=29×9256395 | 28 | 9256395 |
| 31 | 30 | 1073741823=31×34636833 | 30 | 34636833 |
| 33 | 20 | 1048575=33×31775 | 20 | 31775 |
| 35 | 24 | 16777215=35×479349 | 24 | 479349 |
| 37 | 36 | 68719476735=37×1857283155 | 36 | 1857283155 |
| 39 | 24 | 16777215=39×430185 | 24 | 430185 |
この結果から、例えば電卓でaのm=37乗根を求めたいときは、1から始めて「aを1857283155(=q)回掛ける」、「『−−√』ボタンを36(=p)回押す」という2つの操作を何回も繰り返し行えばよいということが分かります。もちろんaを1857283155回を掛けることは普通の電卓、普通の人間ではできないでしょうし、『−−√』ボタンを36回も押すとどんな数から始めても電卓上では1になってしまうと思いますが、これは思考遊びなのでそういうところは気にしません。
まとめ
今回は電卓遊びから派生して、任意の数がメルセンヌ数の約数となるのかどうかという問題について考えました。メルセンヌ数は奇数であるため、偶数の約数を持つわけがなく、結論としては「どんな奇数もあるメルセンヌ数の約数になる。どんな偶数もメルセンヌ数の約数にならない」ということになります。
メルセンヌ数の約数なんてとても難しそうということでほとんど考えていませんでしたが、みうらさんの一言で無事に解決することができました。これは反省すべき点ですが、数論の世界では一見難しそうな問題がいとも簡単に解けてしまったり、一見簡単そうな問題がじつは超絶難問であったという事態はよく起こるのです。例えば次の良く似た2つの問題について考えましょう。
「n2−1の形をした素数は無限個あるか？」
「n2+1の形をした素数は無限個あるか？」
この問題は前者は中学数学で簡単に解決できるのですが、後者は現代数学でも解決されていません。後者の問題は今世紀中に解決するかどうかもわからないのです。
フェルマーの最終定理も一見簡単だが解決までに360年かかかった超絶難問ですよね。数学の世界はとても奥深いです。超絶難問の海で溺れないように気を付けながら、気楽に楽しんでいきましょう。
(文/松中)
「数学教室和(なごみ)」では電卓の使い方からリーマン予想まで、あなたの数学学習を全力サポートします。お問い合わせはこちらから。お問い合わせページへ