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

【 解 答 】

\(x _ n\) を整式 \(x^2-2x-1\) で割った商を \(P(x\) ) , 余りを \(a _ n x+b _ n\) とおく.
\(n=1\) のときについて考えれば \[ a _ 1 = 1 , \ b _ 1 = 0 \quad ... [1] \] また \[\begin{align} x^{n+1} & = x \left\{ (x^2-2x-1) P(x) +a _ n x +b _ n \right\} \\ & = (x^2-2x-1) \left\{ x P(x) +a _ n \right\} +( 2 a _ n +b _ n )x +a _ n \end{align}\] なので \[ a _ {n+1} = 2 a _ n +b _ n , \ b _ {n+1} = a _ n \quad ... [2] \] まず, すべての自然数 \(n\) について

1. [A] : 『 \(a _ n , b _ n\) は整数である. 』

が成立することを, 数学的帰納法を用いて示す.

1. 1*　\(n=1\) のとき
   [1] より, [A] が成立している.

2. 2*　\(n=k\) のとき, [A] が成立すると仮定すると
   [2] より, \(a _ {k+1} , b _ {k+1}\) も整数となり, \(n = k+1\) のときも, [A] は成立する.

以上より, すべての自然数 \(n\) に対して, [A]が成り立つことが示された.
続いて, すべての自然数 \(n\) について

1. [B] : 『 \(a _ n\) と \(b _ n\) をともに割切る素数はない. 』

が成立することを示す.

1. 1*　\(n=1\) のとき
   [1] より [B] は成立する.

2. 2*　\(n \geqq 2\) のときについて, 背理法を用いて示す.
   \(a _ n = kp\) , \(b _ n = mp\) （ \(p\) は素数, \(n , m\) は整数）と表せると仮定すると, [2] より \[\begin{align} a _ {n-1} & = b _ n = mp , \\ b _ {n-1} & = a _ n -2 b _ n = (k+2m)p \end{align}\] したがって, \(a _ {n-1} , b _ {n-1}\) も素数 \(p\) で割切れる.
   しかし, これを繰返すと, \(a _ {1} , b _ {1}\) も素数 \(p\) で割切れることになるが, これは矛盾である.
   ゆえに, [B] が成立する.

以上より, すべての自然数 \(n\) について, [B] が成立する.