数学界で「マスターデーモン」というともうあれしかない、恐ろしい奴です。
1990 IMO 問3
\(\cfrac{2^n+1}{n^2}\)が整数となるような1より大きい整数\(n\)をすべて求めよ。
見た目はシンプルで、中学生も簡単に理解できる問題なのに、
世界中の高校生を悩ませた、デーモン的な存在。
これの攻略をしていきます。
思考過程
まずは、\(n\)に\(2,3,4,5,\cdots\)と代入していきます。
そうすると、\(n\)が偶数だとダメだということが見えてきます。(分子が奇数、分母が偶数となるため)
\(n=15\)くらいまで計算しても、\(n=3\)のときしか整数とならないので、
これが答えかな…?という見当をつけておきます。
しかし分母が\(n^2\)というのは考えにくいなあ。。。
\(n\)が3の倍数であることを示せばいいのではという見当がつきます。
なぜなら、\(n\)は奇数だということが分かっているので、
\(2^n+1=2^n+(-1)^n\)であり、
LTEの
補題を適用するには
\(2-(-1)=3\)の倍数であることが必要だからです。
ここから、こういう発想を思いつくことが難しいのですが、
\(n\)の最小の素因数\(p\)を取ります。(\(n\)は奇数なので\(p \geq 3\)です。)
このとき、\(\frac{2^n+1}{n^2}\)が整数なので
\(2^n \equiv -1 \pmod p\)、そして
\(4^n \equiv 1 \pmod p\)であることがわかります。
\(4^{p-1} \equiv 1 \pmod p\)
よって、\(n\)と\(p-1\)の公約数が4の位数となるわけですが、
\(p\)は\(n\)の最小の素因数なので、\(\gcd(n,p-1)=1\)です。
ここが少しわかりにくいと思うので、解説します。
もし\(n\)と\(p-1\)が2以上の公約数を持ったとすると、
それは\(p-1\)の約数なので\(p\)より小さいことになりますが、
\(p\)は\(n\)の最小の素因数なので、そんな\(n\)の約数は存在しないからです。
したがって\(\gcd(n,p-1)=1\)なので、これが4の位数となり、
すなわち\(4 \equiv 1 \pmod p\)が成り立つので、\(p=3\)です。
これで\(n\)が3の倍数であることがいえました。
\({\rm ord}_p (x^n-y^n) = {\rm ord}_p (x-y)+{\rm ord}_p n\)
LTEの
補題に、\(p=3,x=2,y=-1\)を代入して
\({\rm ord}_3 (2^n-(-1)^n) = {\rm ord}_3 (2-(-1))+{\rm ord}_3 n\)
\({\rm ord}_3 (2^n+1) = {\rm ord}_3 n + 1\)
また、\({\rm ord}_3 n^2 = 2{\rm ord}_3 n\)
\(\frac{2^n+1}{n^2}\)が整数なので、
\({\rm ord}_3 (2^n+1) \geq {\rm ord}_3 n^2\)より
\({\rm ord}_3 n + 1 \geq 2{\rm ord}_3 n\)
\(1 \geq {\rm ord}_3 n\)
また\(n\)は3の倍数なので\({\rm ord}_3 n \leq 1\)であることから、
\({\rm ord}_3 n = 1\)がわかります。
これで\(n\)に結構な制約ができました。
こっからどうすればいいのか、僕は手が止まりましたが…。
同じようなステップを進めてみましょう。
\(n=3\)のときは問題の条件を満たすので、\(n>3\)と仮定します。
\(n\)の2番目に小さい素因数\(q\)を取ります。\(q \geq 5\)です。
\(4^n \equiv 1 \pmod q, 4^{q-1} \equiv 1 \pmod q\)
がそれぞれ成り立ち、\(n\)と\(q-1\)の公約数が4の位数となるわけですが、(\(p=3\)の証明と同様)
\(\gcd(n,q-1)=1 or 3\)が成り立ちます。(\(q\)は2番目に小さい\(n\)の素因数なので)
しかし\(\gcd(n,q-1)=1\)のときは\(4 \equiv 1 \pmod q\)となり\(q=3\)となってしまい、
これはおかしい。
なので\(\gcd(n,q-1)=3\)がわかります。
\(4^3\equiv 1\pmod q\)より\(q\)は63の素因数、このうち\(q>3\)を満たすのは\(q=7\)のみです。
しかし\(n\)は3の倍数なので\(p=3k\)(\(k\)は整数)とおけ、
\(2^n+1\equiv 2^{3k}+1 \equiv 8^k+1 \equiv 1+1 \equiv 2 \pmod 7\)
となり、これは\(2^n+1\)が\(n^2\)で割り切れることに矛盾します。
よって\(n>3\)という仮定が間違っていることがわかり、
背理法で
解は\(n=3\)のみということがわかります。
結論。
難しい。
実際、
LTEの
補題を使う問題は中~高難度のものばかりです。
もしあなたが高レベルに到達したいと思っているのならば、
これは知っていて損はありません。