東京大学 2002年度 前期日程 第2次学力試験文系数学 第2問

(1) $x^{n+1}$ を $x^2-x-1$ で割った余りが $a_{n}x+b_n$ であるから、ある多項式 $Q(x)$ を用いて $$x^{n+1}=(x^2-x-1)Q(x)+a_{n}x+b_n$$ と書ける。両辺にxを掛けると $$x^{n+2}=x(x^2-x-1)Q(x)+a_n{x}^2+b_{n}x$$ である。したがって、$x^{n+2}$ を $x^2-x-1$ で割った余りは、$a_n{x}^2+b_{n}x$ を同じ式で割った余りに等しい。

ここで $x^2-x-1=0$ とみなして余りを計算すれば $x^2\equiv x+1$ である。よって$$\begin{array}{rl}{\displaystyle a_n{x}^2+b_{n}x}& {\displaystyle \equiv a_n(x+1)+b_{n}x}\\ {\displaystyle }& {\displaystyle =(a_n+b_n)x+a_n}\end{array}$$である。したがって $${\displaystyle a_{n+1}=a_n+b_n,b_{n+1}=a_n}$$ を得る。

(2)
まず $n=1$ では、$x^2$ を $x^2-x-1$ で割った余りは $x+1$ である。したがって $a_1=1,b_1=1$ であり、どちらも正の整数で互いに素である。

次に、ある $n$ で $a_n,b_n$ が正の整数であるとする。このとき(1)より $$a_{n+1}=a_n+b_n,b_{n+1}=a_n$$ であるから、$a_{n+1},b_{n+1}$ も正の整数である。よって帰納法により、すべての $n$ で $a_n,b_n$ は正の整数である。

互いに素であることを示す。$a_n,b_n$ が互いに素であると仮定し、$d$ を $a_{n+1},b_{n+1}$ の公約数とする。このとき $$d\mid a_{n+1}=a_n+b_n,d\mid b_{n+1}=a_n$$ である。したがって $d\mid (a_n+b_n)-a_n=b_n$ である。つまり $d$ は $a_n,b_n$ の公約数である。仮定より $a_n,b_n$ は互いに素なので $d=1$ である。

よって $a_{n+1},b_{n+1}$ も互いに素である。初期値 $a_1=b_1=1$ から帰納法により、すべての正の整数 $n$ について $a_n,b_n$ は互いに素である。

余りの係数を更新する写像

係数の組をフィボナッチ数列と同定する。連続するフィボナッチ数の最大公約数は、ユークリッドの互除法で一つ前の組へ戻すと1になる。

(1) $$x^{n+1}\equiv a_{n}x+b_n(\mathrm{m}\mathrm{o}\mathrm{d}{x}^2-x-1)$$の両辺に $x$ を掛け、$x^2\equiv x+1$ を用いると$$x^{n+2}\equiv (a_n+b_n)x+a_n\mathrm{.}$$余りの一意性から$$a_{n+1}=a_n+b_n,b_{n+1}=a_n\mathrm{.}$$(2)$$F_1=F_2=1,F_{j+2}=F_{j+1}+F_j$$ とする。(1)と$$(a_1,b_1)=(1,1)$$から帰納的に$$a_n=F_{n+1},b_n=F_n$$である。したがって両者は正の整数である。

またユークリッドの互除法により$$\gcd (F_{n+1},F_n)=\gcd (F_n,F_{n+1}-F_n)=\gcd (F_n,F_{n-1})\mathrm{.}$$これを繰り返すと$$\gcd (F_{n+1},F_n)=\gcd (F_2,F_1)=1.$$よって $a_n,b_n$ は互いに素である。