東大オープンをLTEの補題で瞬殺する
こんにちは. 東大オープンが近づいていたので先日過去問を解いたところ, 見事にLTEの補題が使えたので記念に投稿しようと思います.
問題は次のような感じでした.
- $n$を正の整数とする. $3^n+4^n$が5の倍数となる時, $3^n+4^n$は$5^2$の倍数であることを示せ.
- $n$を正の整数とする. $3^n+4^n$が$5^3$の倍数となる$n$を全て求めよ.
(1)は地道に計算すれば解けると思います. (2)は(1)の結果をうまく利用すればあっさり解けます.
自分の回答はこんな感じ.
- 少し実験してみる. 表は$\mod{5}$で考えている.
| $n$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| $3^n$ | 3 | 4 | 2 | 1 | 3 | 4 | 2 | 1 |
| $4^n$ | 4 | 1 | 4 | 1 | 4 | 1 | 4 | 1 |
| $3^n+4^n$ | 2 | 0 | 1 | 2 | 2 | 0 | 1 | 2 |
どうやら, $n \equiv 2 \pmod{4} $の時に$3^n+4^n $は$5$の倍数になるらしい. そして, 確かにその時は$5^2$の倍数でもある. これを示すことにする. ここで$f(n)=3^n+4^n$と定めておく.
\begin{eqnarray*}
f(n+4)
&=&3^n\cdot81+4^n\cdot256\\
&\equiv&3^n+4^n\\
&\equiv&f(n)
\end{eqnarray*}
また, 同様にして$f(n+5)\equiv f(n+1), f(n+6)\equiv f(n+2), f(n+7)\equiv f(n+3)$が言えるので, $f(n)$を$5$で割った余りは周期的に変化することがわかる. これと表より
\begin{equation*}
f(n)\equiv0\pmod{5}\iff n\equiv2\pmod{4}
\end{equation*}
が言える.
次に, $n=4m+2(m\in\mathbb{Z}_{\geq0})$の時に$f(n)$が$25$でも割り切れることを示したい. 実際に代入すると
\begin{eqnarray*}
3^{4m+2}+4^{4m+2}
&=&9\cdot3^{4m}+16\cdot4^{4m}\\
&=&9\cdot81^m+16\cdot256^m\\
&\equiv&9\cdot6^m+16\cdot6^m\pmod{25}\\
&\equiv&25\cdot6^m\pmod{25}\\
&\equiv&0\pmod{25}
\end{eqnarray*}
となって, 題意が示された.
- ようやく本題です. ここで使うLTEの補題の主張は次のとおりです.
任意の整数$x,y$と自然数n及びこれらの素因数ではない素数$p$について, 以下が成立する.
$p$が奇素数のとき
- $x-y\equiv0\pmod{p}$のとき
\begin{equation*} v_p(x^n\pm y^n)=v_p(x\pm y)+v_p(n) (複合同順) \end{equation*} - $x+y\equiv0\pmod{p}$かつ$n$が奇数のとき
\begin{equation*} v_p(x^n+y^n)=v_p(x+y)+v_p(n) \end{equation*} - $x+y\equiv0\pmod{p}$かつ$n$が偶数のとき
\begin{equation*} v_p(x^n+y^n)=0 \end{equation*}
また, $p=2$のとき
- $x-y\equiv0\pmod{2}$かつ$n$が偶数なら
\begin{equation*} v_2(x^n-y^n)=v_2\biggl(\frac{x^n-y^n}{2}\biggr)+v_2(n) \end{equation*} - $x-y\equiv0\pmod{2}$かつ$n$が奇数なら
\begin{equation*} v_2(x^n-y^n)=v_2(x-y) \end{equation*}
今, $f(n)$が$125$の倍数であるためには, まず$25$の倍数であることが必要なので, $n=4m+2(m\in\mathbb{Z}_{\geq0})$が必要である.
すると$f(4m+2)=9^{2m+1}+16^{2m+1}$は, $9$も$16$も$5$では割り切れず, $9+16=25$は5で割り切れるのでLTEの補題が適用できて, $2m+1$は奇数なので
\begin{eqnarray*} v_5(f(4m+2)) &=&v_5(9^{2m+1}+16^{2m+1})\\ &=&v_5(9+16)+v_5(2m+1)\\ &=&2+v_5(2m+1) \end{eqnarray*}
$f(4m+2)$が$125$で割れるためにはこの値が$3$以上であれば良いので, 求める条件は$v_5(2m+1)\geq1$である.
また$2m+1$は奇数なので$2m+1=5(2k-1)(k\in\mathbb{N})$と書けることが必要かつ十分. 以上より求める$n$は$n=10(2k-1)(k\in\mathbb{N})$.
いかがだったでしょうか. 僕は正直LTEの補題はうろ覚えだったのですが, 勉強する機会を得ました. 模試が簡単に解けてしまうのは便利ですね! 模範回答は把握していませんが.
拙い文章ですが最後まで読んでくれてありがとうございました. また次の記事でお会いしましょう.
この記事を高評価した人
この記事に送られたバッジ
投稿者
