トップ› 東京大学› 2002年› 理系第2問

東京大学 2002年理系第2問解説

方針・初手

多項式の割り算についての基本的な恒等式を立てる。割られる式を割る式と商、余りを用いて表す。(1) では $x^{n+1}$ の式から $x^{n+2}$ の式を作り出し、余りの一意性を利用して漸化式を導く。(2) は、(1) で得られた漸化式を利用して数学的帰納法で証明する。互いに素であることの証明には、ユークリッドの互除法の原理が有効である。

解法1

(1)

$x^{n+1}$ を $x^2 - x - 1$ で割ったときの商を $Q_n(x)$ とおくと、余りが $a_n x + b_n$ であるから、次の恒等式が成り立つ。

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

この式の両辺に $x$ を掛けると、

$$ \begin{aligned} x^{n+2} &= x \{ (x^2 - x - 1)Q_n(x) + a_n x + b_n \} \\ &= x(x^2 - x - 1)Q_n(x) + a_n x^2 + b_n x \end{aligned} $$

ここで、$x^2 = (x^2 - x - 1) + x + 1$ であるから、これを代入して変形する。

$$ \begin{aligned} x^{n+2} &= x(x^2 - x - 1)Q_n(x) + a_n \{ (x^2 - x - 1) + x + 1 \} + b_n x \\ &= (x^2 - x - 1) \{ x Q_n(x) + a_n \} + a_n(x + 1) + b_n x \\ &= (x^2 - x - 1) \{ x Q_n(x) + a_n \} + (a_n + b_n)x + a_n \end{aligned} $$

$x Q_n(x) + a_n$ は多項式であるから、この式は $x^{n+2}$ を $x^2 - x - 1$ で割ったときの余りが $(a_n + b_n)x + a_n$ であることを示している。

一方で、問題の定義より $x^{n+2}$ を $x^2 - x - 1$ で割った余りは $a_{n+1} x + b_{n+1}$ である。

余りは 1次以下の多項式として一意に定まるため、係数を比較して以下が成り立つ。

$$ \begin{cases} a_{n+1} = a_n + b_n \\ b_{n+1} = a_n \end{cases} $$

(2)

すべての正の整数 $n$ について、「$a_n, b_n$ は共に正の整数で、互いに素である」という命題を $P(n)$ とし、数学的帰納法を用いて証明する。

[1] $n=1$ のとき

$x^{1+1} = x^2$ を $x^2 - x - 1$ で割った余りを求める。

$$ x^2 = (x^2 - x - 1) \cdot 1 + x + 1 $$

より、余りは $x + 1$ である。したがって、$a_1 = 1, b_1 = 1$ となる。

これらは共に正の整数であり、最大公約数は 1 であるため互いに素である。よって、$n=1$ のとき $P(1)$ は成り立つ。

[2] $n=k$ （$k$ は正の整数）のとき、$P(k)$ が成り立つと仮定する。

すなわち、$a_k, b_k$ は共に正の整数で、互いに素であると仮定する。

$n=k+1$ のときを考える。 (1) の結果より、

$$ \begin{cases} a_{k+1} = a_k + b_k \\ b_{k+1} = a_k \end{cases} $$

帰納法の仮定より $a_k \geqq 1, b_k \geqq 1$ であるから、

$$ a_{k+1} = a_k + b_k \geqq 1 + 1 = 2 > 0 $$

$$ b_{k+1} = a_k \geqq 1 > 0 $$

となり、$a_{k+1}$ と $b_{k+1}$ は共に正の整数である。

次に、$a_{k+1}$ と $b_{k+1}$ が互いに素であることを示す。ユークリッドの互除法の原理より、自然数 $A, B$ について $\gcd(A, B)$ を最大公約数とすると、$\gcd(A, B) = \gcd(A - B, B)$ が成り立つ。

$$ \gcd(a_{k+1}, b_{k+1}) = \gcd(a_k + b_k, a_k) = \gcd((a_k + b_k) - a_k, a_k) = \gcd(b_k, a_k) $$

帰納法の仮定より $a_k$ と $b_k$ は互いに素であるから、$\gcd(a_k, b_k) = 1$ である。したがって $\gcd(a_{k+1}, b_{k+1}) = 1$ となり、$a_{k+1}$ と $b_{k+1}$ も互いに素である。

よって、$n=k+1$ のときも $P(k+1)$ は成り立つ。

[1], [2] より、すべての正の整数 $n$ に対して、$a_n, b_n$ は共に正の整数で、互いに素であることが証明された。

解説

多項式の剰余問題では、$A = BQ + R$ の恒等式を立てることが基本である。(1)では、商を文字でおいて $x$ を掛けることで次数を1つ上げ、右辺を $B$ で整理し直すという典型的な処理が問われている。二次方程式 $x^2 - x - 1 = 0$ の解（黄金比に関連する値）を代入して求める方針もあるが、本問では無理数が現れるため、多項式の変形のまま処理したほうが簡明である。

(2)の「互いに素」の証明は、背理法を用いて共通素因数 $p$ を持つと仮定して矛盾を導く方法や、解答のようにユークリッドの互除法の性質 $\gcd(a, b) = \gcd(a-b, b)$ を利用する方法が定石である。漸化式がシンプルであるため、互除法の適用が非常にスムーズにいく。