京都大学 2013年 理系 第3問 解説

方針・初手

• $x^n$ を $x^2-2x-1$ で割った余りの係数を $a_n,\, b_n$ とおき、$x^{n+1} = x \cdot x^n$ の関係から漸化式を導く。
• 「$a_n,\, b_n$ が整数であること」「ともに割り切る素数が存在しないこと」の 2 点をそれぞれ数学的帰納法で証明する。

解法1（帰納法と背理法）

自然数 $n$ について、$x^n$ を $x^2-2x-1$ で割った余りを $a_n x + b_n$ とおく。

$$ x^n = (x^2-2x-1)Q_n(x) + a_n x + b_n \quad \cdots \textcircled{1} $$

両辺に $x$ を掛け、$x^2 = (x^2-2x-1) + 2x + 1$ を利用して整理すると、

$$ x^{n+1} = (x^2-2x-1)\{xQ_n(x) + a_n\} + (2a_n+b_n)x + a_n $$

余りの一意性から係数を比較して、

$$ \begin{cases} a_{n+1} = 2a_n + b_n \\ b_{n+1} = a_n \end{cases} \quad \cdots \textcircled{2} $$

$n=1$ のとき $x^1 = (x^2-2x-1)\cdot 0 + 1\cdot x + 0$ より $a_1=1,\, b_1=0$。

【前半：$a_n,\, b_n$ が整数であることの証明】

数学的帰納法による。

• $n=1$：$a_1=1,\, b_1=0$ は整数。✓
• $a_k,\, b_k$ が整数のとき、$\textcircled{2}$ より $a_{k+1} = 2a_k+b_k$、$b_{k+1}=a_k$ も整数。✓

よってすべての自然数 $n$ について $a_n,\, b_n$ は整数である。$\blacksquare$

【後半：$a_n$ と $b_n$ をともに割り切る素数が存在しないことの証明】

数学的帰納法による。

• $n=1$：$a_1=1$ を割り切る素数は存在しないため、ともに割り切る素数はない。✓

• $n=k$ で成立（$a_k,\, b_k$ をともに割り切る素数が存在しない）と仮定する。

  $n=k+1$ のとき、$a_{k+1}$ と $b_{k+1}$ をともに割り切る素数 $p$ が存在すると仮定する（背理法）。

  $b_{k+1} = a_k$ より $p \mid a_k$。また $b_k = a_{k+1} - 2a_k$ であり、$p \mid a_{k+1}$ かつ $p \mid a_k$ より $p \mid b_k$。

  すると $p$ は $a_k$ と $b_k$ をともに割り切る素数となり、帰納法の仮定に矛盾する。

  よって $a_{k+1}$ と $b_{k+1}$ をともに割り切る素数は存在しない。✓

よってすべての自然数 $n$ について、$a_n$ と $b_n$ をともに割り切る素数は存在しない。$\blacksquare$

解法2（ユークリッドの互除法）

漸化式の導出および $a_n,\, b_n$ が整数であることの証明は解法1と同様。

$\gcd(A, B) = \gcd(A-kB, B)$（$k$ は整数）を用いると、

$$ \gcd(a_{n+1}, b_{n+1}) = \gcd(2a_n+b_n,\, a_n) = \gcd(b_n,\, a_n) = \gcd(a_n, b_n) $$

よって $\gcd(a_n, b_n)$ は $n$ によらず一定であり、$\gcd(a_1, b_1) = \gcd(1, 0) = 1$ であるから、すべての自然数 $n$ について

$$ \gcd(a_n, b_n) = 1 $$

最大公約数が $1$ であることは、$a_n$ と $b_n$ が互いに素であることを意味し、ともに割り切る素数は存在しない。$\blacksquare$

解説

整式の割り算と整数問題を融合した典型問題である。「余りを $a_n x + b_n$ とおき、漸化式を作る」という第一歩が核心である。

後半の証明は解法1の背理法でも解法2の $\gcd$ を使う方針でも論証できるが、解法2のユークリッドの互除法の原理による処理は記述が簡潔で美しい。

答え

略（解法1の証明を参照）