(138) 任意の奇数mと任意の正の整数kである整数nが存在してn^n-mが2^kの倍数

こんばんは。今日はJMOのやつで解説希望があったこれを解きます。

考え方って言われてもだいたい経験則で適当にやっただけですがまあ解説していきます。

まずこの問題で何を考えるかですが、2^kの倍数みたいな話が出てきてるけどこういうのはだいたい2^kの倍数になったnに対してそれをうまく使って2^(k+1)の倍数になることをいう、すなわちkに対する帰納法でやればいけそうなんじゃねってお気持ちになります。

それを念頭におくと

k＝1ならn奇数ならなんでもいいやという感じになって、

k＝2ならn^n-mが4の倍数はm≡1(mod4)ならn＝5とかでいいし、m≡3(mod4)とかならn＝3でいけます。

で、ここからどうしようって感じになるけど、この次にn＝5とか見てみると625-mで例えばm＝1とかなら4の倍数になってくれてます(8の倍数にはなってません)。一方、n＝3とかみると、3^3-m＝27-mで、これはもしm＝3とかなら8の倍数にまでなります。

それゆえ単純な構成にはならないなあと思うわけですが、ここで冷静になると2でいっぱい割り切れる分には問題なくて、「2^kの倍数だが2^(k+1)の倍数にならない」のようなケースの時にのみうまくなんか施してやらばいいんじゃない？てなります。それを踏まえると、2^kの倍数になることがくずれなさそうな2^k+nのようなものを考えると、(2^k+n)^(2^k+n)は二項定理展開とかn^(2^k)が2^(k+1)の倍数になることとか念頭においたら2^(k+1)の倍数になってくれそうなことがわかります。

あとは帰納法として答案に昇華すればいけます。