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

整数 $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)\right) \\ &= 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, \\\therefore\quad2^{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$．

どう論証してもこのくらいの複雑さにはなると思います。