2010年 日本数学オリンピック本選 第２問 解答例
$${k}$$を正の整数、$${m}$$を奇数とする。このとき$${n^n-m}$$が$${2^k}$$で割り切れるような正の整数$${n}$$が存在することを示せ。
考え方：
まず$${n}$$は奇数でないといけないことは明らかです。
$${2^k}$$で割り切れる値は当然$${2^1, 2^2, \cdots 2^{k-1}}$$でも割り切れますから、
上手く$${n}$$を選ぶことで$${n^n -m}$$が$${2}$$で割れる回数をどんどん大きくできる、
そんな$${n}$$の構成方法がある、
ということを示すのが良さそうです。
$${m = 3}$$で実験してみると、
$${n=3}$$のとき$${3^3 - 3 = 24}$$は$${2^3}$$で割り切れ、
$${n=5, n=7, n=9}$$あたりはめぼしい結果を生みませんが、
$${n=11}$$のとき$${11^{11}-3}$$は（やや面倒な計算の末）$${2^4}$$で割り切れることがわかります。
ここで、$${11 = 3+ 2^3}$$に気づきます。
これをとっかかりに、
$${n^n - m}$$が$${2^k}$$で割り切れるとき、
$${2^k}$$で割り切れることを保ちつつ、
さらにもう一回$${2}$$で割れるようにしたいということから
$${n+2^k}$$を新たに$${n}$$としたらいいことがあるのではと感じます。
これを試してみるとうまくいきましたので、解答例としました。
他にもうまい構成方法があるかもしれません。
解答例:
ある正の奇数$${n_0}$$について$${n_0^{n_0}-m}$$は偶数になるため、
$${n_0^{n_0}-m}$$が$${2^{k_0}}$$で割り切れるが
$${2^{k_0+1}}$$で割り切れないような正の整数$${k_0}$$がとれる。
このとき、
$$
\begin{align*}
n_0^{n_0}-m &\equiv 2^{k_0} (\text{mod} 2^{k_0+1})\\
\iff -m & \equiv 2^{k_0} - n_0^{n_0} (\text{mod} 2^{k_0+1})
\end{align*}
$$
となる。
さて、$${n=2^{k_0} + n_0}$$としたとき、
$$
\begin{align*}
(2^{k_0} + n_0)^{2^{k_0}+n_0} - m & \equiv 2^{k_0} n_0^{2^{k_0}+n_0 - 1}(2^{k_0}+n_0) + n_0^{2^{k_0}+n_0} - m (\text{mod } 2^{k_0+1}) \\
& \equiv 2^{k_0} n_0^{2^{k_0}+n_0} + n_0^{2^{k_0}+n_0} - m (\text{mod } 2^{k_0+1}) \\
& \equiv 2^{k_0} n_0^{2^{k_0}+n_0} + n_0^{2^{k_0}+n_0} +2^{k_0} - n_0^{n_0} (\text{mod } 2^{k_0+1})\\
& \equiv 2^{k_0} (n_0^{2^{k_0}+n_0} + 1) + n_0^{n_0}(n_0^{2^{k_0}} - 1) (\text{mod } 2^{k_0+1})\\
\end{align*}
$$
となるが、$${(n_0^{2^{k_0}+n_0} + 1)}$$は偶数になるので
$$
2^{k_0} (n_0^{2^{k_0}+n_0} + 1) \equiv 0 (\text{mod }2^{k_0+1})
$$
であり、また、
$$
\begin{align*}
n_0^{2^{k_0}} - 1 & = (n_0^{2^{k_0-1}} + 1)(n_0^{2^{k_0-2}} + 1)\cdots (n_0 + 1)(n_0 - 1)\\
& \equiv 0 (\text{mod } 2^{k_0+1})
\end{align*}
$$
である（$${n_0}$$が奇数であるため右辺の各括弧内が偶数になることを用いた。）
よって
$$
\begin{align*}
(2^{k_0} + n_0)^{2^{k_0}+n_0} - m & \equiv 2^{k_0} (n_0^{2^{k_0}+n_0} + 1) + n_0^{n_0}(n_0^{2^{k_0}} - 1) (\text{mod } 2^{k_0+1})\\
& \equiv 0 (\text{mod } 2^{k_0+1})
\end{align*}
$$
を得る。
以上より、任意の奇数$${n}$$について
$${n^n -m}$$を$${2^{k_0}}$$が割り切る最大の正の整数$${k_0}$$に対し、
$${2^{k_0} +n}$$を改めて$${n}$$とすることで、
$${n^n -m}$$が$${2^{k_0+1}}$$で割り切れるようにすることができる。
この操作を有限回繰り返すことで、任意の正の整数$${k}$$に対して、
$${n^n -m}$$が$${2^k}$$で割り切れるような$${n}$$を構成することができる。
コメント:
指数が絡む問題で「割り切れる」を議論するとき、
二項展開しての議論は必須になりますね。
やや面倒ですが、ミスがないように・・・。
お知らせ：
少しでも興味深い、楽しいと感じたらぜひスキやコメント、フォローください！
他に公開している記事などの一覧はこちら
ぜひ初めに見てください。｜光捷 (note.com)