京都大学 理系 2013年度 第3問 解説
問題編
問題
n を自然数とし、整式 $x^n$ を整式 $x^2-2x-1$ で割った余りを $ax+b$ とする。このとき a と b は整数であり、さらにそれらをともに割り切る素数は存在しないことを示せ。
考え方
余りをきれいな形で書くのは難しいので、数学的帰納法を使って示しましょう。 $x^k$ を割ったときの余りと $x^{k+1}$ を割ったときの余りの関係性を考えましょう。
解答編
問題
n を自然数とし、整式 $x^n$ を整式 $x^2-2x-1$ で割った余りを $ax+b$ とする。このとき a と b は整数であり、さらにそれらをともに割り切る素数は存在しないことを示せ。
解答
k を自然数とする。 $x^k$ を $x^2-2x-1$ で割ったときの商を $Q_k(x)$ とし、余りを $a_k x+b_k$ とする。このとき、\[ x^k=(x^2-2x-1)Q_k(x) +a_k x +b_k \]と書ける。また、
\begin{eqnarray}
x^{k+1}
&=&
x\cdot x^k \\[5pt]
&=&
x \left\{(x^2-2x-1)Q_k(x) +a_k x +b_k\right\} \\[5pt]
&=&
(x^2-2x-1)x Q_k(x) +a_k x^2 +b_k x \\[5pt]
&=&
(x^2-2x-1)x Q_k(x) \\
& & +a_k (x^2-2x-1) +2a_k x +a_k +b_k x \\[5pt]
&=&
(x^2-2x-1) (x Q_k(x)+a_k) \\
& & +(2a_k+b_k)x +a_n \\[5pt]
\end{eqnarray}と書けることから、
\begin{eqnarray}
a_{k+1} &=& 2a_k+b_k \\[5pt]
b_{k+1} &=& a_k \\[5pt]
\end{eqnarray}が、すべての自然数 k に対して成り立つ。この関係式を (*) で表す。
まず、 $a_n,b_n$ が整数であることを示す。
$a_1=1$, $b_1=0$ なので、 $n=1$ のとき、 $a_n,b_n$ はともに整数である。
$n=k$ のとき $a_k,b_k$ がともに整数であるとすると、 (*) の関係式から、 $a_{k+1},b_{k+1}$ もともに整数であることがわかる。
よって、数学的帰納法により、すべての自然数 n について、 $a_n$, $b_n$ が整数であることがわかる。
また、ある自然数 k について、もし $a_{k+1}$, $b_{k+1}$ がともにある素数 p で割り切れるとすると、(*) から\[ a_k=b_{k+1} \]なので、 $a_k$ も p の倍数であり、\[ b_k=a_{k+1}-2a_k \]から、 $b_k$ も p の倍数となる。これを繰り返していくと、 $a_1,b_1$ も p の倍数となるが、これらの値は $1$ と $0$ なので、ともに割り切るような素数 p は存在しない。よって、どの自然数 k に対しても、 $a_k$, $b_k$ をともに割り切る素数 p は存在しない。
以上から、 $x^n$ を整式 $x^2-2x-1$ で割った余り $ax+b$ について、 a と b は整数であり、これらをともに割り切る素数が存在しないことが示された。
（終）
解説
整式を整式で割る問題では、割る式が $0$ になるような値を x に代入することが多いです。剰余の定理を使う方法ですね。
しかし、今の場合なら、 $x=1\pm\sqrt{2}$ を代入することになり、計算が煩雑になります。ここでは、数学的帰納法が使えればよく、 $x^k$ を割ったときの余りと $x^{k+1}$ を割ったときの余りの関係性がきれいに導けるので、剰余の定理を使う方法は避けたほうがいいでしょう。
漸化式が導ければ、示すべきことはほぼ明らかです。整数であることはすぐにわかります。また、ともに割り切る素数がないことも、漸化式を逆に使う（ $k+1$ の式から $k$ の式を表現する）ことで示すことができます。
