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