トップ› 北海道大学› 1993年› 文系第1問

北海道大学 1993年文系第1問解説

方針・初手

(1)は指定通り数学的帰納法を用いて証明する。指数部分 $b(n)=2^n$ が満たす性質 $2 \cdot b(n) = b(n+1)$ に注意して、和と差の積を展開する処理を行う。 (2)の前半は、(1)の結論と $a_{n+1}$ の定義式を比較すれば直ちに導ける。後半は、前半で示した関係式を利用し、最大公約数を文字で置いて矛盾を導く背理法を用いる。

解法1

(1) $n \geqq 1$ に対する命題「$a_0a_1 \cdots a_n = 2^{b(n+1)} - 1$」を (A) とする。

[1] $n=1$ のとき

左辺は $a_0 a_1$ である。与えられた定義より、

$$ a_0 = 2^{b(0)} + 1 = 2^{2^0} + 1 = 3 $$

$$ a_1 = 2^{b(1)} + 1 = 2^{2^1} + 1 = 5 $$

であるから、左辺は $3 \times 5 = 15$ となる。

右辺は、

$$ 2^{b(1+1)} - 1 = 2^{2^2} - 1 = 16 - 1 = 15 $$

となり、左辺と右辺が一致する。よって、$n=1$ のとき (A) は成り立つ。

[2] $n=k$ ($k \geqq 1$) のとき (A) が成り立つと仮定する。

すなわち、

$$ a_0a_1 \cdots a_k = 2^{b(k+1)} - 1 $$

が成り立つとする。

$n=k+1$ のとき、左辺を計算すると、

$$ \begin{aligned} a_0a_1 \cdots a_k a_{k+1} &= (a_0a_1 \cdots a_k) a_{k+1} \\ &= (2^{b(k+1)} - 1) (2^{b(k+1)} + 1) \\ &= (2^{b(k+1)})^2 - 1^2 \\ &= 2^{2 \cdot b(k+1)} - 1 \end{aligned} $$

ここで、指数の部分は、

$$ 2 \cdot b(k+1) = 2 \cdot 2^{k+1} = 2^{k+2} = b(k+2) $$

となるため、

$$ a_0a_1 \cdots a_{k+1} = 2^{b(k+2)} - 1 $$

となり、$n=k+1$ のときも (A) は成り立つ。

[1], [2] より、数学的帰納法によって、$n \geqq 1$ のすべての整数に対して $a_0a_1 \cdots a_n = 2^{b(n+1)} - 1$ が成り立つことが示された。

(2) まず、$a_{n+1} = a_0a_1 \cdots a_n + 2$ を示す。

$n \geqq 1$ のとき、(1) の結果より、

$$ a_0a_1 \cdots a_n = 2^{b(n+1)} - 1 $$

である。また定義より、

$$ a_{n+1} = 2^{b(n+1)} + 1 $$

である。これら2式の差をとると、

$$ \begin{aligned} a_{n+1} - a_0a_1 \cdots a_n &= (2^{b(n+1)} + 1) - (2^{b(n+1)} - 1) \\ &= 2 \end{aligned} $$

したがって、移項して整理すると、

$$ a_{n+1} = a_0a_1 \cdots a_n + 2 $$

が成り立つ。

次に、$l > m \geqq 1$ のとき、$a_l$ と $a_m$ が $1$ より大きい公約数を持たないことを示す。

$a_l$ と $a_m$ が $1$ より大きい公約数 $d$ を持つと仮定する。

$l > m \geqq 1$ より $m \leqq l-1$ であるから、積 $a_0a_1 \cdots a_{l-1}$ は因数として $a_m$ を含む。したがって、$d$ は $a_m$ の倍数である積 $a_0a_1 \cdots a_{l-1}$ も割り切る。

前半で示した等式において $n = l-1$ （$l > 1$ より $n \geqq 1$ を満たす）とすると、

$$ a_l = a_0a_1 \cdots a_{l-1} + 2 $$

これを変形して、

$$ 2 = a_l - a_0a_1 \cdots a_{l-1} $$

となる。

仮定より $d$ は $a_l$ と $a_0a_1 \cdots a_{l-1}$ の両方を割り切るため、その差である $2$ も割り切らなければならない。 $d$ は $d > 1$ を満たす正の整数であるから、$d = 2$ となる。

しかし、すべての $n \geqq 0$ において、

$$ a_n = 2^{2^n} + 1 $$

であり、偶数に $1$ を加えた数であるから $a_n$ は常に奇数である。したがって $a_l$ も $a_m$ も奇数であり、$2$ を公約数に持つことはできない。これは $d=2$ であることに矛盾する。

よって、$a_l$ と $a_m$ は $1$ より大きい公約数を持たないことが示された。

解説

本問で登場する数列 $a_n = 2^{2^n} + 1$ は「フェルマー数」と呼ばれる有名な数列である。 (1) は指数の計算規則 $2^m \times 2^m = 2^{2m}$ と、和と差の積 $(X-1)(X+1)=X^2-1$ を組み合わせる典型的な帰納法の問題である。 (2) では、前半で導いた関係式 $a_l - a_0a_1 \cdots a_{l-1} = 2$ を用いて、ユークリッドの互除法と同様の論理で公約数の候補を絞り込むアプローチが重要となる。一方が他方を含む積の形で表されていることに着目し、差をとって定数（本問では2）だけを残すことで、公約数がその定数の約数に限られることを示す手法は、整数の証明問題における常套手段である。