読者です 読者をやめる 読者になる 読者になる

数学徘徊記

自由な数学ブログ。

マスターデーモンに挑戦

数学界で「マスターデーモン」というともうあれしかない、恐ろしい奴です。

1990 IMO 問3
\(\cfrac{2^n+1}{n^2}\)が整数となるような1より大きい整数\(n\)をすべて求めよ。

見た目はシンプルで、中学生も簡単に理解できる問題なのに、
世界中の高校生を悩ませた、デーモン的な存在。 

これの攻略をしていきます。 

思考過程

まずは、\(n\)に\(2,3,4,5,\cdots\)と代入していきます。
そうすると、\(n\)が偶数だとダメだということが見えてきます。(分子が奇数、分母が偶数となるため)

 

\(n=15\)くらいまで計算しても、\(n=3\)のときしか整数とならないので、
これが答えかな…?という見当をつけておきます。

 

しかし分母が\(n^2\)というのは考えにくいなあ。。。

 

ここで

su-hai.hatenablog.com

を使うことを考えると、
\(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の倍数であることがいえました。

 

というわけで、LTEの補題を使います。

 

\({\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補題を使う問題は中~高難度のものばかりです。
もしあなたが高レベルに到達したいと思っているのならば、
これは知っていて損はありません。