2010年京都大学理系第5問の整数問題です。サイトやら参考書やらを漁ってみましたが、全て同じ解法をとっていて、面白くあ

Question

2010年京都大学理系第5問の整数問題です。

サイトやら参考書やらを漁ってみましたが、全て同じ解法をとっていて、面白くありません。

自分は最初、 $3^a-1=(4-1)^a-1$ と見て二項定理からなんとかいこうとしましたが、実力不足なのか複雑すぎるのか、うまく論証できず今モヤモヤ中です。

ちなみに模範回答は全て、(1)を帰納法で、(2)は $m=2^nk$ と置いてやっています。

自分の解法でうまく論証できれば一番簡単な解法だと思います。

自分の正しいかどうかわからない回答もはっつけておきます。

整数が得意な方お願いします🤲🤲🤲

Accepted Answer

整数 $x$ に含まれる素因数 $p$ の重複度を $p$-進付値といい，$v_p(x)$ と書きます。 例．$v_2(32) = 5$，$v_7(98) = 2$，$v_5(11) = 0$  問題 (1) は $3^a – 1$ の $2$-進付値を評価する問題です。 問題 (2) は $3^m – 1$ の $2$-進付値を評価する部分が本題です。  整数 $n$ の $p$-進付値を評価するには次のようにします。 １．$n$ を因数分解， ２．$v_p(x)$ の対数的ふるまい（$v_p(xy) = v_p(x) + v_p(y)$）によって積を和に変換， ３．項をそれぞれ適切な法（$p$-進付値を考えているのだから当然 $p$ のべき乗を法にとる）のもとで評価。 以下の解答例ではこの手順にしたがいます。  (1) $3^{2^n} - 1$ を因数分解して， $$ \begin{aligned} v_2(3^{2^n} - 1)  &= v_2\left((3^2 - 1) (3^2 + 1) (3^{2^2} + 1) \cdots (3^{2^{n - 1}} + 1)ight) \  &= v_2(3^2 - 1) + \sum_{k = 1}^{n - 1} v_2(3^{2^k} + 1)． \end{aligned} $$ ここで $3^{2^k} + 1 \equiv (-1)^{2^k} + 1 \equiv 2 \pmod{4}$ であるから，$v_2(3^{2^k} + 1) = 1$．したがって， $$ v_2(3^{2^n} - 1)    = v_2(3^2 - 1) + n - 1   = n + 2． $$  (2) $m = 2^n M,\ (2,M) = 1$ とおく． $$ \begin{aligned} v_2(3^m - 1)  &= v_2(3^{2^n} - 1) + v_2(3^{2^n (M - 1)} + 3^{2^n (M - 2)} + \cdots + 1)． \end{aligned} $$ ここで $3^{2^n} \equiv 1 \pmod{2}$ であるから，$3^{2^n (M - 1)} + 3^{2^n (M - 2)} + \cdots + 1 \equiv M \equiv 1 \pmod{2}$．したがって， $$ \begin{aligned} v_2(3^m - 1)  &= v_2(3^{2^n} - 1) + 0 = n + 2 = v_2(m) + 2． \end{aligned} $$ 仮定より $2^m \mid 3^m - 1$ であるから， $$ \def\arraystretch{1.5} \begin{array}{c} m \leqq v_2(3^m - 1) = v_2(m) + 2 \leqq \log_2 m + 2, \ 	herefore\quad 2^{m - 2} / m \leqq 1． \end{array} $$ $f(m) = 2^{m - 2} / m$ は $m \geqq 1$ で単調増加，かつ $f(5) > 1$ であるから，$m \geqq 5$ においてこの不等式は成り立たない．すなわち $m = 2$ または $m = 4$．  どう論証してもこのくらいの複雑さにはなると思います。  補足: しいて二項展開で議論する場合は次のように展開します。 $$   3^{2^n} - 1 = (2 + 1)^{2^n} - 1 = \sum_{k = 1}^{2^n} \binom{2^n}{k} 2^k $$ これは $3^{2^n} - 1$ の $2$-進表示，ただし各桁がキャリーオーバーした $2$-進表示になっています。キャリーオーバーを上位の桁へ移してみると下位の桁にちょうど $n + 2$ 個の $0$ が並ぶことが証明できます。議論の中核は二項係数 $\binom{2^n}{1}, \binom{2^n}{2}, \binom{2^n}{3}$ の $2$-進付値を評価することです。

@DoubleExpYui · Answer

この回答でも悪くないと思うけど、いくつか添削 (1)最後の$2^{m+2}(	ext{偶数}+1)$のところはもう少し計算過程を分かりやすくした方がいい。一つ前の式の最後の項は確かに$2^{m+2}$の倍数だが、他の項はどうかが一目で分かりにくい。  (2)「$4m$が$2^m$で割り切れることが必要」のあと 必要→必要と並べるよりはこっちの方がいいかな 「また、このとき$2^m\leqq4m$が必要」→「つまり$2^m\leqq4m$を満たす$m$を求めればよい」  グラフは文字じゃないので、きちんと「グラフより」などと書く方がいい 「(グラフ)より$m=2,4$が必要」→「グラフより$m\leq4$であるから、$m=2,4$」  最後の検算のところは、べつに逆をとっているわけではないので 「逆にこの時～なので証明終り」→「$m=2$のとき～、$m=4$のとき…だから確かに正しい(証明終り)」  個人的な考えだから参考程度にして欲しい。