解説

方針・初手

余りを扱う問題なので、合同式の考え方を用いる。割る式が $x^2-x-1$ であるから、

$$ x^2 \equiv x+1 \pmod{x^2-x-1}

$$

として、$x^{n+1}$ の余りから $x^{n+2}$ の余りを求める。

解法1

$x^{n+1}$ を $x^2-x-1$ で割った余りが $a_nx+b_n$ であるから、

$$ x^{n+1} \equiv a_nx+b_n \pmod{x^2-x-1}

$$

である。

両辺に $x$ をかけると、

$$ x^{n+2} \equiv a_nx^2+b_nx \pmod{x^2-x-1}

$$

となる。ここで、

$$ x^2 \equiv x+1 \pmod{x^2-x-1}

$$

であるから、

$$ \begin{aligned} x^{n+2} &\equiv a_n(x+1)+b_nx \\ &= (a_n+b_n)x+a_n \end{aligned} \pmod{x^2-x-1}

$$

を得る。

一方、$x^{n+2}$ を $x^2-x-1$ で割った余りは定義より $a_{n+1}x+b_{n+1}$ である。余りは一意に定まるので、

$$ a_{n+1}=a_n+b_n,\qquad b_{n+1}=a_n

$$

である。

次に、$a_n,b_n$ が正の整数で互いに素であることを数学的帰納法で示す。

まず $n=1$ のとき、

$$ x^2=(x^2-x-1)+(x+1)

$$

であるから、

$$ a_1=1,\qquad b_1=1

$$

である。したがって $a_1,b_1$ はともに正の整数であり、互いに素である。

次に、ある正の整数 $n$ について、$a_n,b_n$ がともに正の整数で、互いに素であると仮定する。このとき、(1)で示した関係式より、

$$ a_{n+1}=a_n+b_n,\qquad b_{n+1}=a_n

$$

である。

帰納法の仮定より $a_n,b_n$ は正の整数なので、$a_n+b_n$ も正の整数である。したがって $a_{n+1},b_{n+1}$ はともに正の整数である。

また、

$$ \gcd(a_{n+1},b_{n+1}) =\gcd(a_n+b_n,a_n)

$$

である。ここで、ユークリッドの互除法より、

$$ \gcd(a_n+b_n,a_n)=\gcd(b_n,a_n)

$$

である。帰納法の仮定より $\gcd(a_n,b_n)=1$ だから、

$$ \gcd(a_{n+1},b_{n+1})=1

$$

となる。

よって、$a_{n+1},b_{n+1}$ も互いに素である。

以上より、数学的帰納法によって、すべての正の整数 $n$ に対して、$a_n,b_n$ はともに正の整数であり、互いに素である。

解説

この問題の中心は、割る式 $x^2-x-1$ から

$$ x^2 \equiv x+1 \pmod{x^2-x-1}

$$

と見られる点である。余りを直接計算するのではなく、$x^{n+1}$ の余りから $x^{n+2}$ の余りを作ると、漸化式が自然に得られる。

互いに素であることは、漸化式

$$ a_{n+1}=a_n+b_n,\qquad b_{n+1}=a_n

$$

がユークリッドの互除法と相性がよいことを利用する。すなわち、和を取っても最大公約数は

$$ \gcd(a_n+b_n,a_n)=\gcd(b_n,a_n)

$$

と保たれる。

答え

**(1)**

$$ a_{n+1}=a_n+b_n,\qquad b_{n+1}=a_n

$$

である。

**(2)**

すべての正の整数 $n$ に対して、$a_n,b_n$ はともに正の整数であり、互いに素である。