京大 2013年前期理系第3問 - 数式で独楽する

$n,k$ を自然数とする。整式 $x^n$ を整式 $x^2 -2x -1$ で割った余りを $ax + b$ とする。このとき $a$ と $b$ は整数であり、さらにそれらをともに割り切る素数は存在しないことを示せ。

整式 $x^n$ を、整式 $Q_n(x)$ を用いて
\begin{equation}
x^n = (x^2 -2x -1)Q_n(x) + a_n x + b_n \tag{1}
\end{equation}と表すこととします。

$n=1$ の場合、式(1)より
\begin{equation}
x = a_1 x + b_1
\end{equation}なので、係数を比較して
\begin{eqnarray}
a_1 &=& 1 \\
b_1 &=& 0
\end{eqnarray}を得ます。
$a_1, \ b_1$ は整数であり、共に割り切る素数は存在しません。(A)

一方、式(1)より、
\begin{eqnarray}
x^{n+1} &=& (x^2 -2x -1)Q_{n+1}(x) + a_{n+1}x + b_{n+1} \tag{2} \\
x^{n+1} &=& x(x^2 -2x -1)Q_n (x) + a_n x^2 + b_n x \\
&=& (x^2 -2x -1)(x + a_n)Q_n (x) + (2a_n + b_n)x + a_n \tag{3}
\end{eqnarray}が得られます。*1
式(2), (3)の係数を比較して、
\begin{eqnarray}
a_{n+1} &=& 2a_n + b_n \tag{4} \\
b_{n+1} &=& a_n \tag{5}
\end{eqnarray}を得ます。

これより、
$a_n, \ b_n$ が整数であれば、 $a_{n+1}, \ b_{n+1}$ も整数となります。(B1)

また、 $a_{n+1}, \ b_{n+1}$ を共に割り切る素数 $p$ が存在すると仮定し、
\begin{eqnarray}
a_{n+1} &=& \alpha p \\
b_{n+1} &=& \beta p
\end{eqnarray}とします。
式(4), (5)により、
\begin{eqnarray}
a_n &=& \beta p \\
b_n &=& a_{n+1} - 2a_n = (\alpha -2\beta)p
\end{eqnarray}を得ます。
つまり、 $a_n, \ b_n$ は共に $p$ で割り切れることになります。
繰り返していくと、 $a_1, \ b_1$ も $p$ で割り切れることになります。
ところが、これは $a_1 = 1, \ b_1 = 0$ に矛盾します。
よって $a_n, \ b_n \ (n = 1,2, \cdots)$ を割り切る素数は存在しない(B2)
ことが分かります。

以上、(A), (B1), (B2)より、
$a,b$ は共に整数であり、共に割り切る素数は存在しない
ことが示されました。

解説

本問は、 $x^n$ を式(1)の形に書くことが鍵になります。
これができると式(2), (3)は容易に導くことができ、 $a,b$ を式(4), (5)の形に書くことができます。
あとは、数学的帰納法と背理法(悖理法、帰謬法)で攻略することになります。
背理法 - 数式で独楽する
 数学的帰納法 - 数式で独楽する

ちなみに、 $x,y$ の最大公約数を $\mathrm{gcm}(x,y)$ と書くことにすると*2、式(4), (5)と互除法により、
\begin{eqnarray}
\mathrm{gcm}(a_{n+1}, \ a_n) &=& \mathrm{gcm}(a_n, \ b_n) \\
\mathrm{gcm}(a_{n+1}, \ b_{n+1}) &=& \mathrm{gcm}(a_{n+1}, \ a_n)
\end{eqnarray}となり、
\begin{eqnarray}
\mathrm{gcm}(a_{n+1}, \ b_{n+1}) &=& \mathrm{gcm}(a_n, \ b_n) \\
& \vdots & \\
&=& \mathrm{gcm}(a_1, \ b_1) = \mathrm{gcm}(1,0) = 1
\end{eqnarray}となります。

*1:一方は式(1)に $n+1$ を、他方は式(1)の両辺を $x$ 倍しています。

*2:Greatest Common Measureの略です。