[別館]球面倶楽部零八式markIISR

東大入試数学中心。解説なので解答としては不十分。出題年度で並ぶようにしている。大人の解法やうまい解法は極めて主観的に決めている。

2002年(平成14年)東京大学前期-数学(理科)[2]

2024.02.13記

[2] $n$ は正の整数とする． $x^{n+1}$ を $x^2-x-1$ で割った余りを $a_nx+b_n$ とおく．

(1) 数列 $a_n$ ， $b_n$ ， $n=1$ ， $2$ ， $3$ ，…，は
$\left\{\begin{array}{l} a_{n+1}=a_n+b_n \\ b_{n+1}=a_n \end{array}\right.$
を満たすことを示せ．

(2) $n=1$ ， $2$ ， $3$ ，… に対して， $a_n$ ， $b_n$ は共に正の整数で，互いに素であることを証明せよ．

2021.01.17記
フィボナッチ数列の隣合う項は互いに素．

[解答]
(1) $x^{n+2}$ を $x^2-x-1$ で割った余りは $x(a_nx+b_n)$ を $x^2-x-1$ で割った余りに等しく， $an(x+1)+b_nx=(a_n+b_n)x+a_n$ であるから，
$a_{n+1}=a_n+b_n$ ， $b_{n+1}=a_n$
をみたす．

(2) (1)より， $b_{n+2}=b_{n+1}+b_{n}$ （ $n\geqq 1$ ）が成立する． $b_1=b_2=1$ より，任意の自然数 $n$ について $b_n$ は整数であり， $a_n=b_{n+1}$ であるから， $a_n$ も整数である．

また，ユークリッドの互除法により， $b_{n+2}$ と $b_{n+1}$ の最大公約数は， $b_n=b_{n+2}-b_{n+1}$ と $b_{n+1}$ の最大公約数に等しく，これは帰納的に $b_2$ と $b_1$ の最大公約数 $1$ に等しい．よって $b_{n+1}=a_n$ と $b_n$ は互いに素である．