京都大学 2010年 理系 第5問（乙） 解説

方針・初手

(1) 「$A$ は $2^s$ で割り切れるが、$2^{s+1}$ で割り切れない」という条件は、「$A = 2^s \cdot L$ （$L$ は奇数）」と表せることと同値です。この形に定式化し、数学的帰納法を用いて証明を進めます。

(2) 与えられた正の偶数 $m$ を、$m = 2^n \cdot k$ （$n$ は正の整数、$k$ は奇数）という形に設定し、式 $3^m - 1$ から素因数 $2$ をいくつ括り出せるか（2進付値）を考えます。(1) の結果と、$x^k - 1$ の因数分解を活用します。

解法1

(1)

「$3^{2^n} - 1 = 2^{n+2} \cdot L_n$ （$L_n$ は奇数）と表せること」を、数学的帰納法によって示す。

[1] $n=1$ のとき

$3^2 - 1 = 8 = 2^3 \cdot 1$ であり、$2^{1+2} = 2^3$ で割り切れ、$2^{1+3} = 2^4$ では割り切れない。よって $L_1 = 1$（奇数）となり、成り立つ。

[2] $n=j$（$j$ は正の整数）のとき成り立つと仮定する。

すなわち、$3^{2^j} - 1 = 2^{j+2} \cdot L_j$（$L_j$ は奇数）と表せると仮定する。

$n=j+1$ のときを考えると、

$$ 3^{2^{j+1}} - 1 = (3^{2^j})^2 - 1 = (3^{2^j} - 1)(3^{2^j} + 1) $$

帰納法の仮定より、第1因数は $3^{2^j} - 1 = 2^{j+2} \cdot L_j$ である。

第2因数について考えると、

$$ 3^{2^j} + 1 = (3^{2^j} - 1) + 2 = 2^{j+2} \cdot L_j + 2 = 2(2^{j+1} \cdot L_j + 1) $$

ここで、$j \geqq 1$ より $j+1 \geqq 2$ であるから、$2^{j+1} \cdot L_j$ は偶数である。 よって、$M_j = 2^{j+1} \cdot L_j + 1$ は奇数である。

これらを掛け合わせると、

$$ 3^{2^{j+1}} - 1 = (2^{j+2} \cdot L_j) \cdot 2M_j = 2^{j+3} \cdot L_j M_j $$

$L_j, M_j$ はともに奇数であるから、その積 $L_j M_j$ も奇数である。 したがって、$n=j+1$ のときも成り立つ。

[1], [2] より、すべての正の整数 $n$ について、$3^{2^n} - 1$ は $2^{n+2}$ で割り切れるが $2^{n+3}$ では割り切れないことが示された。（証明終）

(2)

$m$ は正の偶数であるから、$m = 2^n \cdot k$（$n$ は正の整数、$k$ は奇数）と表すことができる。 このとき、

$$ 3^m - 1 = 3^{2^n \cdot k} - 1 = (3^{2^n})^k - 1 $$

$A = 3^{2^n}$ とおくと、$A$ は奇数であり、

$$ A^k - 1 = (A - 1)(A^{k-1} + A^{k-2} + \cdots + A + 1) $$

と因数分解できる。ここで、$A-1 = 3^{2^n} - 1$ は、(1) より素因数 $2$ をちょうど $n+2$ 個もつ。

一方、第2因数 $A^{k-1} + A^{k-2} + \cdots + A + 1$ は、奇数 $A$ の累乗の和であり、項数は $k$ 個（奇数）である。奇数を奇数個足し合わせた和は奇数となるため、この第2因数は奇数である（素因数 $2$ をもたない）。

したがって、$3^m - 1$ がもつ素因数 $2$ の個数は、ちょうど $n+2$ 個である。

条件より $3^m - 1$ は $2^m$ で割り切れるので、素因数 $2$ の個数は $m$ 以上でなければならない。

$$ n+2 \geqq m = 2^n \cdot k $$

$k$ は正の奇数より $k \geqq 1$ であるから、

$$ n+2 \geqq 2^n $$

これを満たす正の整数 $n$ を探す。

• $n=1$ のとき：$3 \geqq 2k$ となり、奇数 $k$ は $k=1$ のみ。このとき $m = 2^1 \cdot 1 = 2$。
• $n=2$ のとき：$4 \geqq 4k$ となり、奇数 $k$ は $k=1$ のみ。このとき $m = 2^2 \cdot 1 = 4$。
• $n \geqq 3$ のとき：二項定理を用いると、

$$ 2^n = (1+1)^n \geqq 1 + n + \frac{n(n-1)}{2} $$

$n \geqq 3$ のとき $\dfrac{n(n-1)}{2} \geqq 3$ であるから、

$$ 2^n \geqq n + 1 + 3 = n + 4 > n + 2 $$

となり、$n+2 \geqq 2^n$ を満たす $n$ は存在しない。

以上より、$m=2$ または $m=4$ であることが示された。（証明終）

解説

素因数 $p$ がいくつ含まれるか（$p$ 進付値）に着目する整数問題の頻出テーマです。

(1) では $a^2 - b^2 = (a-b)(a+b)$ を利用して次数を下げていく手法が鍵となります。帰納法の中で「奇数であること」を文字式で明示的に定義しながら進めると、論理の飛躍を防げます。

(2) では「偶数 $m$ を $2^n \cdot k$（$k$ は奇数）とおく」という定石を用いています。さらに、「奇数の累乗の和」について「項数が奇数個（$k$ 個）だから全体の和も奇数」と判断する処理は、因数分解を用いた整数問題で非常によく使われる考え方です。

答え

(1)

, (2) ともに題意が示された。（証明終）