皆さん、こんにちは。
今回は、「マスターデーモン」と呼ばれる整数問題を紹介します。
マスターデーモンは、国際数学オリンピック（以下「数オリ」）で出題された上のような問題で、世界中の数学強者が挑む数オリの数ある過去問の中でも「シンプルかつ超難問」としてよく知られている問題です。
ちなみに、幾多もの大学入試を解いてきた私も、数オリの問題は全く歯が立たず、今回のマスターデーモンも自力では解けておりません。執筆にあたっては、以下のブログ記事を参考にさせて頂きました。討伐！マスターデーモン！！｜大島学習塾のホームページ (oshima-gakushujuku.com)
0.まずは小問に分ける
この問題は、もし分母と分子が逆であれば超絶簡単な問題に化けます。基本的に指数関数の方が2次関数よりも大きくなるので、もし分母と分子が逆なら「分子≧分母」になるnはレアケースなので簡単に絞り込め、あとは各候補を虱潰しに代入するだけでよくなります。
しかし、今回の場合は基本的に「分子≧分母」なので上のような絞り込みができません。条件を緩くして分母を1乗にしたとしてもnが2^n +1を割り切る条件を絞り込むのは容易じゃありません。
すぐに分かるのは「nは奇数じゃないといけない」ということです。何故かというと、分子は必ず奇数になるので、もしnが偶数だと分母に2が約分されずに残ってしまうからです。よって、nは奇数だけ考えればOKです。
そのもとでnに具体的な数を入れて実験してみると、
という感じになり、分子は常に3で割り切れ、2^n +1の3以外の素因数とnは互いに素になっていることが予想できます。条件を満たすnはどうもn=3だけのようですね。
このように答えを予想するだけなら簡単なのですが、いざそれを証明しようとすると中々難しいです。
元々は上のような1行の問題文なのですが、ノーヒントで解くにはあまりに厳しすぎるので、誘導も兼ねていくつかの小問に分解します。
(1)は難関大の入試であれば出題されててもおかしくない難易度ですが、特に(2)が大学入試でも使わないような発想が要求され難しい問題になっています。(3)以降は(2)までができていればあまり難しくありません。
このように小問に分けても十分すぎるほどの超難問なわけです・・・
1. (1)について
これは、kについての数学的帰納法を考えれば証明できる小問で、旧帝大レベルであれば入試に出てきても不思議じゃない難易度です。
まず、nは3でk回割り切れる奇数だと言っているので、
のようにおけます。
kについての数学的帰納法で考えるので、k=0の場合を最初に調べてしまいます。
2項定理を利用すると、
のように2^n +1は3×「3で割り切れない整数」となるので、3でちょうど1回割り切れることが分かります。
次にk=lのときに題意を満たすと仮定してk=l+1の場合を調べると、
3乗の展開式によってk=l+1の場合も題意を満たすことが分かります。
これで数学的帰納法で証明完了です。
この結果を(4)で利用してn=3に絞り込んでいくことになります。
2. (2)について
この小問が最大の山場で、完全に大学入試の範疇を超えた問題です（内容自体は高校数学の範囲ですが）。
当たり前の話ですが、2^n +1がn^2で割り切れるなら、当然少なくとも2^n +1はnで割り切れるはずです。
そして、2^n +1は、nを構成する全ての素因数で割り切れないとおかしいわけです。
nを構成する素因数のうち最小のものをp(≧3)とすると少なくとも2^n +1はpで割り切れるはずなので、そんなpが実が3でないといけないことを証明していきます。
2^n +1がpで割り切れることを数式にすると、⑤のような合同式になります。
次が閃きポイントなのですが、
となるような最小の自然数xを考えます。例えばp=5なら、x=2です。
⑤と⑥はほぼ同じ式なので、このxを使ってnがどんな式で書けるのかを考えていきます。具体的には、n÷xの商をa, 余りをbとして
と表せるとして検討していきます。bはn÷xの余りなので0≦b<xとなっていることがポイントです。
このとき、a,bの条件を調べると、⑧のようになります。
aが-1の肩に乗っているので、aの偶奇で場合分けしそうですね。場合分けしてみましょう。
aが偶数の時は、⑧は
となり、⑥と同じような式になります。xより小さい自然数bでこの関係が成り立ってしまっているので、xの最小性に反し矛盾します。よって、aが偶数の時はNGです。
aが奇数の時は、⑧は
となり、b=0なら成り立っています。
b>0のときは、天下りですが下のような指数を考えると⑥に帰着できます。
無理やり「1」を指数の形にして、指数がxになるようにするわけです。
そうすると、またしても⑥と同じ形の⑪が出て来ますが、aが偶数の時と全く同じロジックで矛盾します。
結局、⑧は「aが奇数かつb=0」の時しか成り立たないことが分かりました。特にb=0という結論が重要で、⑦に代入すると、
結局xはnの約数だと分かりました。
ここで、さらなる飛び道具を用意します。それが「フェルマーの小定理」です。
この定理の証明はRSA暗号 ～素数は世の中でメチャクチャ役に立っている～ - ちょぴん先生の数学部屋 (hatenablog.com)に載せておりますが、数オリの問題なので既知の定理だとして証明なしで使ってしまいます。
フェルマーの小定理を使うと
が言えるので（2とpは当然互いに素です）、これを使ってx<pであることを示します。
x≧pを仮定すると、下のような指数を考えると⑬が示せます。
これが例によって⑥と矛盾するので、背理法により
が言えることになります。
ここまでの議論から、
・pはnの最小の素因数（＝pは1より大きいnの最小の約数）※pの定義
・xはnの約数
・xはpより小さい
という3つの結論が得られました。
ということは、xはpより小さいnの約数、つまりx=1しかありえないことが分かります。
この結果をxを定義した⑥に代入すると、
となり、翻訳すれば「3はpで割り切れる」となります。そうなる素数pは3しかないですね。
以上からnの最小の素因数pが3だとわかったので、nは少なくとも3の倍数だと示せました。
この(2)だけでも大学入試では使わないような考え方・発想がいくつも出てくるので、流石は数オリという感じです。
3. (3)について
(2)の結果からnは3の倍数だとわかったので、
と書くことができます。
まずn=3つまりm=1のときは、最初に実験した通りanは整数になります。
次にm≧3の場合を考えるわけですが、(2)と同じような方法で考えればよいです。つまり、mの最小の素因数をq(≧3)とすると、2^n +1 = 8^m +1 は少なくともqで割り切れるはずです。結局、(2)で指数関数の底が2だったものを8に置き換えればいいだけなので、全く同じ議論ができます。
(2)と同じ議論なので詳細は繰り返さず結論だけ書くと、
つまり「9はqで割り切れる」となります。そうなる素数qは、やはり3しかありません。
よって、mも3の倍数になるので、トータルでnは9の倍数だと分かります。
ここまでくれば、ゴールは目前です。
4. (4)について
最初に「答えはn=3だけだろう」と予想しました。(3)までで「n=3」か「nは9の倍数」の2択に絞れているので、後者の「nは9の倍数」が実はNGだと言えればゴールです。
その手段に使うのが、最初に証明した(1)です。
具体的には、分子の3の個数と分母の3の個数を比べて「nが9の倍数だと分母の3の数が多くなってしまって約分しきれない」ことを示します。
nが3でk(≧2)回割り切れるとすると、(1)の結果から2^n+1は3でk+1回割り切れるんでした。
ということは、分子の3はk+1個あって、分母の3は2k個あることになります。
k≧2のときはk+1<2kなので、分母の3が必ず多くなって約分しきれず残ってしまいます。よって、nが9の倍数の時anは整数になりません。
以上から、anが整数になる正の奇数nはn=3だけだと示せました！！これにて終了です。
誘導をつけてもこの超難易度だったわけですから、元のノーヒント1行ではなおさら超難問になるのも当然ですね・・・・
