討伐！マスターデーモン！！
2021年11月4日
数学業界（？）で「マスターデーモン」と呼ばれている整数の超難問があります。
次の問題です：
先日，Twitterでこの問題と再会しました。
「再会」と言ったのは，この問題はいろいろな数学の本で取り上げられている有名な問題で，解いたことはないものの存在は知っていたからです。
でもマスターデーモンと呼ばれていることは知りませんでした（正確には，かつて読んだことがあるけど忘れていました^^;）。
この記事では，この超難問を解説します。
できるだけ少ない予備知識で理解できるように，よく知られた整数論の結果なども証明を補いながら，高校数学の知識があれば分かるような解説を試みます。
また，この難問がマスターデーモンというインパクトのある名前で呼ばれるようになったいきさつについて私が調べたことや，調べていくうちに出会った整数論の公式についてもご紹介します。
次の問題です：
問題
$\dfrac{2^n+1}{n^2}$ が整数となるような $1$ より大きい整数 $n$ をすべて決定せよ。
「再会」と言ったのは，この問題はいろいろな数学の本で取り上げられている有名な問題で，解いたことはないものの存在は知っていたからです。
でもマスターデーモンと呼ばれていることは知りませんでした（正確には，かつて読んだことがあるけど忘れていました^^;）。
この記事では，この超難問を解説します。
できるだけ少ない予備知識で理解できるように，よく知られた整数論の結果なども証明を補いながら，高校数学の知識があれば分かるような解説を試みます。
また，この難問がマスターデーモンというインパクトのある名前で呼ばれるようになったいきさつについて私が調べたことや，調べていくうちに出会った整数論の公式についてもご紹介します。
マスターデーモン，その名の由来
マスターデーモン…インパクトのある名前ですね。そんな名前で呼ばれている数学の超難問があると聞いたら，是非解いてみたいと思う魅力的な名前です^^
マスターデーモンという名前は広く知られているようで（私は知らなかったケド^^;）「マスターデーモン」で検索すると，いろいろなページが見つかります。
「マスターデーモン」という名前のルーツを探るべく，まずは上位に表示された「高校数学の美しい物語」さんの記事を見てみました。
- 「高校数学の美しい物語」さんは，数学の様々な分野に関して解説しているサイトです。読むだけで勉強になるすばらしい記事が満載です^^
いきなりヒントが見つかりましたね！幸い『数学オリンピック事典』は我が家の本棚に飾られていたので，早速該当する箇所を調べてみました。
『事典』の解説では，この超難問をボスキャラの「龍」に見立てて，この問題を２つの補題に分割してそれぞれを「東の塔」と「西の塔」とし，それぞれの最上階にいる「マスターデーモン」を倒せば，本丸の「龍」も倒せるというストーリーが書かれています。
「マスターデーモン」という呼び名の起源が見つかりましたね^^
でもこのストーリーだと本問は「マスタードラゴン」と呼んだ方が正しい気もしますが…^^;
それと『事典』のこの部分を読んでみて，過去にこの部分を読んだことがあるなぁ～と思い出しました。
「マスターデーモン」という名には既に出会っていたのですね！
「マスターデーモン」の由来が分かったので，次節からは解説をしようと思います。
でもその前に少しだけ前置きを^^
今回の解説では，できるだけ少ない予備知識で解ける解法を選択しました。
必要な知識としては，高校数学にプラスして，合同式は中心的な役割をするので必要になります。
大学入試問題でも，合同式を知らないと解けない問題はないかもしれませんが，知っていると有利なのは間違いないので，習得することをオススメします^^
合同式については当塾の「数学公式集」に重要な性質をまとめてあります： 合同式以外では二項定理と数学的帰納法を使います。両方とも苦手としている高校生が多い項目ですが，必要知識は文理共通の範囲に収まっていると思います。
逆に，以下の解説を通じて合同式，二項定理，数学的帰納法の扱いについて一皮むけてくれることを期待しています^^
$n$ は $3$ の倍数
それでは解説を始めましょう。問題の条件から $n$ を絞り込んできます。
$\dfrac{2^n+1}{n^2}$ が整数になるということは，$2^n+1$ は $n^2$ で割り切れます。$2^n+1$ は奇数なので，割り切れるためには $\boldsymbol{n}$ は奇数でなければなりません。
そこで以下では $n$ は奇数であるとします。まずは $n$ に小さい方から奇数を代入していって様子を見ましょう。
\[\begin{align*}
2^3+1&=9=3^2\\
2^5+1&=33=3\times 11\\
2^7+1&=129=3\times 43\\
2^9+1&=513=3^3\times 19\\
2^{11}+1&=2049=3\times 683\\
2^{13}+1&=8193=3\times 2731\\
2^{15}+1&=32769=3^2\times 11\times 331\\
2^{17}+1&=131073=3\times 43691
\end{align*}\]
これらの計算から，$2^n+1$ は常に $3$ の倍数になりそうだと予想されます。さらに $n$ 自身が $3$ の倍数のときに注目すると，$2^n+1$ は $3$ で2回以上割り切れます。
実は，「$2^n+1$ は $n$ よりも $3$ で１回だけ多く割り切れる」ということが成り立ちます。この事実が問題解決の最後のカギになります。
さて，上で計算した $2^n+1$ の素因数分解を眺めると，$3$ 以外で小さな素因数があまり登場しないように見えます。$2^n+1$ が $n^2$ で割り切れるとき，当然ですが $n$ の素因数すべてで $2^n+1$ が割り切れる必要があります。そこで，$n$ の素因数に注目していきましょう。
$n$ が問題の条件を満たすとし，$\boldsymbol{n}$ の素因数で最小のものを $\boldsymbol{p}$ とします。$n$ は $1$ より大きい奇数なので $p\geqq 3$ です。
- ここで，$p$ を $n$ の素因数で「最小のもの」としたのがポイントです。何か文字を定義するとき，最大とか最小とか極端な性質をもつものを選ぶとよいことがあります。例えば，何かの条件を満たす数が存在しないことを示すのに，そのような数が存在するとして，その条件を満たす最小の数を選んで議論を進めていくうちに，最小として選んだものより小さいものが見つかると，矛盾が導かれたことになり，そもそもそんな条件を満たす数は存在しなかったことが示されたことになります。特に，整数の問題でこのような考え方が役に立つことが多いです。
合同式を使って書くと，
\[ 2^n+1\equiv 0\,\,(\mathrm{mod}\,\,p)\quad\text{すなわち}\quad 2^n\equiv -1\,\,(\mathrm{mod}\,\,p) \]
です。ここで $x$ を $2^x\equiv -1\,\,(\mathrm{mod}\,\,p)$ となる最小の正の整数とします。この $x$ が $n$ の約数であることを示します。$n$ を $x$ で割ったときの商を $a$，余りを $b$ とし，
\[ n=xa+b\quad (0\leqq b\lt x) \]
と表します。$b=0$ を示すのが目標です。このとき，
\[\begin{align*}
2^n=2^{xa+b}=(2^x)^a\cdot 2^b\equiv (-1)^a\cdot 2^b\equiv -1\,\,(\mathrm{mod}\,\,p)
\end{align*}\]
となります。
$b=0$ となることを示すために，$a$ が偶数の場合と奇数の場合に分けて考えます。
まず $a$ が偶数のとき，$(-1)^a\equiv 1\,\,(\mathrm{mod}\,\,p)$ より $2^b\equiv -1\,\,(\mathrm{mod}\,\,p)$ となりますが，$x$ が $2^x\equiv -1\,\,(\mathrm{mod}\,\,p)$ となる最小の正の整数であることと $b\lt x$ より $b=0$ となるしかありません。
続いて $a$ が奇数のとき，$(-1)^a\equiv -1\,\,(\mathrm{mod}\,\,p)$ より $-2^b\equiv -1\,\,(\mathrm{mod}\,\,p)$ すなわち $2^b\equiv 1\,\,(\mathrm{mod}\,\,p)$ となります。
ここで，もし $b\geqq 1$ だとすると，$0\lt x-b\lt x$ であり，
\[ 2^{x-b}\equiv 2^{x-b}\cdot 2^b=2^x\equiv -1\,\,(\mathrm{mod}\,\,p) \]
となりますが，これは $x$ が $2^x\equiv -1\,\,(\mathrm{mod}\,\,p)$ となる最小の正の整数であったことに矛盾します。よってこの場合も $b=0$ です。$b=0$ が示されたので，$n=xa$ つまり $x$ は $n$ の約数であることが分かりました。
さらに $x$ を絞り込んでいくために二項定理を使った計算を行います。
\begin{align*}
2^p&=(1+1)^p={}_p\mathrm{C}_0+{}_p\mathrm{C}_1+{}_p\mathrm{C}_2+\cdots\cdots+{}_p\mathrm{C}_{p-1}+{}_p\mathrm{C}_p\\
&=1+{}_p\mathrm{C}_1+{}_p\mathrm{C}_2+\cdots\cdots+{}_p\mathrm{C}_{p-1}+1\\
&=2+\textstyle\sum\limits_{i=1}^{p-1}{}_p\mathrm{C}_i
\end{align*}
ここで，$\sum$ の各項の ${}_p\mathrm{C}_i$ について，
\[ {}_p\mathrm{C}_i=\dfrac{p\,!\,}{i\,!\,(p-i)\,!\,}=\dfrac{p}{i}\cdot\dfrac{(p-1)\,!\,}{(i-1)\,!\,\{(p-1)-(i-1)\}\,!\,}=\dfrac{p}{i}{}_{p-1}\mathrm{C}_{i-1} \]
より $i{}_p\mathrm{C}_i=p{}_{p-1}\mathrm{C}_{i-1}$ であり，$p$ が素数であることと $1\leqq i\leqq p-1$ より $p$ と $i$ は互いに素なので，${}_p\mathrm{C}_i$ は $p$ の倍数であることが分かります。よって，
\[ 2^p=2+\textstyle\sum\limits_{i=1}^{p-1}{}_p\mathrm{C}_i\equiv 2+\textstyle\sum\limits_{i=1}^{p-1}0=2\,\,(\mathrm{mod}\,\,p) \]
です。$p$ は奇数なので $p$ と $2$ は互いに素であり，合同式の両辺を $2$ で割って，
\[ 2^{p-1}\equiv 1\,\,(\mathrm{mod}\,\,p) \]
が得られます。
- これはフェルマーの小定理という定理の特別な場合です。$p$ を素数とし，$a$ を $p$ と互いに素な正の整数とするとき，$a^{p-1}\equiv 1\,\,(\mathrm{mod}\,\,p)$ が成り立ちます。
\[ 2^{x-p+1}\equiv 2^{x-p+1}\cdot 2^{p-1}=2^x\equiv -1\,\,(\mathrm{mod}\,\,p) \]
となって，$x$ が $2^x\equiv -1\,\,(\mathrm{mod}\,\,p)$ を満たす最小の正の整数であることに矛盾します。よって，$x\lt p$ です。
$x$ は $n$ の約数であることを上で示しましたが，$x$ は $n$ の最小の素因数 $p$ よりも小さいことも分かったので $x=1$ になるしかありません。
このとき，$2^1=2\equiv -1\,\,(\mathrm{mod}\,\,p)$ すなわち $3\equiv 0\,\,(\mathrm{mod}\,\,p)$ なので，$3$ が $p$ の倍数となり $p=3$ が得られます。
よって，$\boldsymbol{n}$ は $\boldsymbol{3}$ の倍数であることが分かりました。
$n\gt 3$ は $9$ の倍数
前節の議論により $n=3m\,(\text{$m$ は正の奇数})$ と表されることが分かりました。特に $m=1$ のとき，$n=3$ であり，
\[ \dfrac{2^3+1}{3^2}=1 \]
となるので，この場合は問題の条件を満たします。$n=3$ 以外の解を探すため，$m\gt 1$ とし，$m$ の最小の素因数を $q$ とします。$m$ は奇数なので $q\geqq 3$ です。
このとき，
\[ 2^n+1=2^{3m}+1=(2^3)^m+1=8^m+1\equiv 0\,\,(\mathrm{mod}\,\,q) \]
より，$8^m\equiv -1\,\,(\mathrm{mod}\,\,q)$ です。ここからは前節と同様の議論を行います。
$8^y\equiv -1\,\,(\mathrm{mod}\,\,q)$ を満たす最小の正の整数 $y$ をとります。$y$ が $m$ の約数であることを示します。
$m$ を $y$ で割ったときの商を $c$，余りを $d$ とすると，
\[ m=yc+d\quad (0\leqq d\lt y) \]
であり，
\[ 8^m=8^{yc+d}=(8^y)^c\cdot 8^d\equiv (-1)^c\cdot 8^d\equiv -1\,\,(\mathrm{mod}\,\,q) \]
となります。
$d=0$ を示すために，前節と同様に $c$ が偶数の場合と奇数の場合に分けて考えます。
まず $c$ が偶数のとき，$(-1)^c\equiv 1\,\,(\mathrm{mod}\,\,q)$ より $8^d\equiv -1\,\,(\mathrm{mod}\,\,q)$ となりますが，$y$ が $8^y\equiv -1\,\,(\mathrm{mod}\,\,q)$ となる最小の正の整数であることと $d\lt y$ より $d=0$ となるしかありません。
続いて $c$ が奇数のとき，$(-1)^c\equiv -1\,\,(\mathrm{mod}\,\,q)$ より $-8^d\equiv -1\,\,(\mathrm{mod}\,\,q)$ すなわち $8^d\equiv 1\,\,(\mathrm{mod}\,\,q)$ となります。
ここで，もし $d\geqq 1$ だとすると，$0\lt y-d\lt y$ であり，
\[ 8^{y-d}\equiv 8^{y-d}\cdot 8^d=8^y\equiv -1\,\,(\mathrm{mod}\,\,q) \]
となりますが，これは $y$ が $8^y\equiv -1\,\,(\mathrm{mod}\,\,q)$ を満たす最小の正の整数であったことに矛盾します。よってこの場合も $d=0$ です。$d=0$ が示されたので，$m=yc$ つまり $y$ は $m$ の約数であることが分かりました。
前節と同様，ここからさらに $y$ の値を絞り込んでいきましょう。
前節で，一般の奇素数 $p$ に対して $2^p\equiv 2\,\,(\mathrm{mod}\,\,p)$ を示したので，当然 $2^q\equiv 2\,\,(\mathrm{mod}\,\,q)$ です。
この合同式の両辺を $3$ 乗すると，
\[ (2^q)^3=8^q\equiv 8\,\,(\mathrm{mod}\,\,q) \]
となります。$q$ は奇素数なので $8$ と互いに素であり，合同式の両辺を $8$ で割って，
\[ 8^{q-1}\equiv 1\,\,(\mathrm{mod}\,\,q) \]
が得られます。ここで，$y\geqq q$ であるとすると，$0\lt y-q+1\lt y$ であり，
\[ 8^{y-q+1}\equiv 8^{y-q+1}\cdot 8^{q-1}=8^y\equiv -1\,\,(\mathrm{mod}\,\,p) \]
となって，$y$ が $8^y\equiv -1\,\,(\mathrm{mod}\,\,q)$ を満たす最小の正の整数であることに矛盾します。よって，$y\lt q$ です。
$y$ は $m$ の約数であることを上で示しましたが，$y$ は $m$ の最小の素因数 $q$ よりも小さいことも分かったので $y=1$ になるしかありません。
このとき，$8^1=8\equiv -1\,\,(\mathrm{mod}\,\,q)$ すなわち $9\equiv 0\,\,(\mathrm{mod}\,\,q)$ なので，$9$ が $q$ の倍数となり $q$ が素数であることから $q=3$ が得られます。
よって，$m$ は $3$ の倍数であることが分かり，$n=3m$ より，$\boldsymbol{n}$ は $\boldsymbol{9}$ の倍数であることが分かりました。
$n=3$
前節までの結果をまとめると，まず $n=3$ は解になります。また，$3$ よりも大きい解があるとすると，それは $9$ の倍数になることも示しました。
本節では，$9$ の倍数が解になることはあり得ないことを示し，解が $n=3$ のみであることを証明します！
そのために，冒頭でも述べた次の命題を証明します：
命題
正の奇数 $n$ が $3$ でちょうど $k$ 回割り切れるとき，$2^n+1$ は $3$ でちょうど $k+1$ 回割り切れる。
命題を，$k$ に関する数学的帰納法で示します。
まず $k=0$ のとき，$l=1$ では明らかに成り立つので，$l\geqq 5$ として，
\begin{align*}
2^n+1&{}=2^l+1=(3-1)^l+1\\
&{}=\textstyle\sum\limits_{k=0}^{l}{}_l\mathrm{C}_k 3^{l-k}\cdot(-1)^k+1\\
&{}=\textstyle\sum\limits_{k=0}^{l-2}{}_l\mathrm{C}_k 3^{l-k}\cdot(-1)^k+{}_l\mathrm{C}_{l-1}3^1\cdot(-1)^{l-1}+{}_l\mathrm{C}_l3^0\cdot(-1)^l+1\\
&{}=\textstyle\sum\limits_{k=0}^{l-2}{}_l\mathrm{C}_k 3^{l-k}\cdot(-1)^k+3l\\
\end{align*}
ここで，$\sum$ の各項は $3$ で $2$ 回以上割り切れますが，最後の項 $3l$ のみ $3$ で $1$ 回しか割り切れないので，全体として $2^n+1$ は $3$ でちょうど$1$ 回割り切れます。よって，$k=0$ のときは命題は正しいと分かります。
次に，ある非負整数 $k$ で命題が成り立っていると仮定し，$n=3^{k+1}l$ のときを考えましょう。
このとき，$3^k l$に対しては命題が成り立つので，$3$ の倍数でない奇数 $m$ が存在し，
\[ 2^{3^k l}+1=3^{k+1}m \]
と表されます。これを用いると，
\begin{align*}
2^n+1&{}=2^{3^{k+1}l}+1=(2^{3^k l})^3+1=(3^{k+1}m-1)^3+1\\
&{}=3^{3k+3}m^3-3^{2k+3}m^2+3^{k+2}m
\end{align*}
第１・第２の項は $3$ で $k+3$ 回以上割り切れますが，最後の項は $3$ で $k+2$ 回しか割り切れないので，全体として $2^n+1$ は $3$ でちょうど $k+2$ 回割り切れます。よって，$k+1$ のときも命題は正しいと分かります。
以上のことから，数学的帰納法により命題は示されました。
ここまでくればゴールまであと少しです^^
前節までの議論により，$n=3$ 以外の解は，整数 $k(\geqq 2)$ と $3$ の倍数でない奇数 $l$ を用いて，$n=3^k l$ と表されます。
このとき，命題により，分子 $2^n+1$ は $3$ でちょうど $k+1$ 回割り切れます。
一方，分母は $n^2=3^{2k} l^2$ なので $3$ でちょうど $2k$ 回割り切れます。
分子が分母で割り切れるためには，分子が $3$ で割り切れる回数が分母が $3$ で割り切れる回数以上にならなければなりません。すなわち，
\[ k+1\geqq 2k\quad\Longrightarrow\quad k\leqq 1 \]
ですが，これは $k\geqq 2$ に反します。以上により，$n$ が $9$ の倍数のときは解になり得ないことが分かり，$\boldsymbol{n=3}$ のみが解であることが示されました。
これにて，マスターデーモン討伐成功です！！
お疲れさまでした^^！！
おわりに
以上，マスターデーモンの解説を行いました。シンプルな問題なのに，整数論のいろいろなテクニックを駆使しなければ解けない手ごわい問題でしたね^^
冒頭でも述べた通り，できるだけ少ない予備知識で理解できる解法を目指しました。
高校数学の範囲を超えないようにかつ，できるだけ１つ１つのステップを追いやすいように丁寧に解説しました…結果，すごく長くなってしまいました^^;
この記事の準備のために，我が家にあったいくつかの書籍やウェブサイトを参照しました。
その中で，いくつかの整数論の（高度な）公式を，この問題に適用している例に出会いました。
最後にそれらの中から２つだけご紹介しようと思います。
是非，意欲的な読者はそれらの公式の証明や，ここでは紹介しきれなかった他の解法なども学び，真の「デーモンスレイヤー」を目指してください^^
位数の法則
素数 $p$ と整数 $a$ に対し，$a^e\equiv 1\,\,(\mathrm{mod}\,\,p)$ を満たす最小の正の整数 $e$ を，$\boldsymbol{p}$ を法とする $\boldsymbol{a}$ の位数という。$p$ を法とする $a$ の位数を $e$ とするとき，
整数 $m$ が $a^m\equiv 1\,\,(\mathrm{mod}\,\,p)$ を満たすならば，$m$ は $e$ の倍数となる。
特に，フェルマーの小定理より，$p-1$ は $e$ の倍数である。
このとき，$2^n\equiv -1\,\,(\mathrm{mod}\,\,p)$ より $4^n\equiv 1\,\,(\mathrm{mod}\,\,p)$ であり，$p$ を法とする $4$ の位数を $e$ とすると，$e$ は $n$ と $p-1$ の約数であるが，$p$ が $n$ の最小の素因数であることから $e=1$ である。よって，$4^1\equiv 1\,\,(\mathrm{mod}\,\,p)$ より，$p=3$ である。特に，$n=3$ は解である。
次に，$n=3m$（$m\geqq 3$ は奇数）の形の解を探す。$m$ の最小の素因数を $q\geqq 3$ とする。
このとき，$2^n=2^{3m}=8^m\equiv -1\,\,(\mathrm{mod}\,\,q)$ より $64^m\equiv 1\,\,(\mathrm{mod}\,\,q)$ であり，$q$ を法とする $64$ の位数を $f$ とすると，$f$ は $m$ と $q-1$ の約数であるが，$q$ が $m$ の最小の素因数であることから $f=1$ である。よって，$64^1\equiv 1\,\,(\mathrm{mod}\,\,q)$ より，$q=3$ または $q=7$ であるが，$q=7$ とすると，$8\equiv 1\,\,(\mathrm{mod}\,\,7)$ より $8^m\equiv -1\,\,(\mathrm{mod}\,\,7)$ に矛盾するので $q=3$ である。
よって，$n=3$ 以外の解があるとすれば $n=3^k l$（$k$ は2以上の整数，$l$ は $3$ の倍数でない奇数）の形である。
LTEの補題
$0$ でない整数 $n$ と素数 $p$ に対し，$n$ が $p$ で割り切れる回数を，$\mathrm{ord}_p n$ と表す。$p$ を奇素数，$n$ を正の整数とする．$p$ の倍数でない整数 $x$，$y$ が $x\equiv y\,\,(\mathrm{mod}\,\,p)$ を満たすとき，
\[ \mathrm{ord}_p(x^n-y^n)=\mathrm{ord}_p(x-y)+\mathrm{ord}_p n \]
が成り立つ．
\begin{align*}
\mathrm{ord}_3(2^n+1)&{}=\mathrm{ord}_3\{2^n-(-1)^n\}=\mathrm{ord}_3\{2-(-1)\}+\mathrm{ord}_3 n\\
&{}=\mathrm{ord}_3 3+\mathrm{ord}_3 3^k l=1+k
\end{align*}
なので，分子 $2^n+1$ は $3$ で $k+1$ 回割り切れる。一方，分母 $n^2=3^{2k} l^2$ は $3$ で $2k$ 回割り切れるので， \[ k+1\geqq 2k \quad\Longrightarrow\quad k\leqq 1 \] となり，$k\geqq 2$ に矛盾する。
コメントを残す