数学界で「マスターデーモン」というともうあれしかない、恐ろしい奴です。
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-(-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の倍数であることがいえました。
というわけで、LTEの補題を使います。
\({\rm ord}_p (x^n-y^n) = {\rm ord}_p (x-y)+{\rm ord}_p n\)
\({\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\)のみということがわかります。
