2東京大学 2002年 数学 第2問解答・解説

$f(x)=x^2-x-1$ とおくと、$f(x)=0$ を用いた余りの計算では $x^2\equiv x+1$ である。$n=1$ のとき $x^{n+1}=x^2$ なので、$a_1=b_1=1$ である。

(1) $n\ge1$ とする。定義から $x^{n+1}\equiv a_nx+b_n$ であるから、両辺に x を掛け、$x^2\equiv x+1$ を用いると $$\begin{aligned}x^{n+2}&\equiv x(a_nx+b_n)=a_nx^2+b_nx\\&\equiv a_n(x+1)+b_nx=(a_n+b_n)x+a_n.\end{aligned}$$ 余りは次数が 2 未満の一次式として一意に定まるので、$a_{n+1}=a_n+b_n$、$b_{n+1}=a_n$ である。

(2) 初項は $a_1=b_1=1$ で正の整数である。$a_n,b_n$ が正の整数なら、$a_{n+1}=a_n+b_n$ と $b_{n+1}=a_n$ も正の整数である。よって数学的帰納法により、すべての $n\ge1$ で $a_n,b_n$ は正の整数である。

さらに、ユークリッドの互除法の性質から $$\gcd(a_{n+1},b_{n+1})=\gcd(a_n+b_n,a_n)=\gcd(b_n,a_n)=\gcd(a_n,b_n).$$ 初項では $\gcd(a_1,b_1)=\gcd(1,1)=1$ であるため、この等式を繰り返し用いて $\gcd(a_n,b_n)=1$ がすべての $n\ge1$ で成り立つ。