解説

方針・初手

$x^2-2x-1$ で割った余りを考えるので、合同式

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

$$

を使って、$x^n$ の余りを漸化式で追う。

余りを $a_nx+b_n$ と書き、$a_n,b_n$ が整数であることと、$\gcd(a_n,b_n)=1$ であることを同時に示す。

解法1

$x^n$ を $x^2-2x-1$ で割った余りを

$$ a_nx+b_n

$$

とおく。すなわち

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

$$

である。

まず $n=1$ のとき

$$ x\equiv 1\cdot x+0

$$

より

$$ a_1=1,\qquad b_1=0

$$

である。

次に、$x^2\equiv 2x+1$ を用いる。$x^n\equiv a_nx+b_n$ の両辺に $x$ をかけると

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

$$

であり、ここで $x^2\equiv 2x+1$ を代入すると

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

$$

となる。したがって

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

$$

である。

$a_1=1,\ b_1=0$ は整数であり、$a_n,b_n$ が整数ならば上の漸化式から $a_{n+1},b_{n+1}$ も整数である。よって数学的帰納法により、すべての自然数 $n$ について $a_n,b_n$ は整数である。

次に、$a_n,b_n$ をともに割り切る素数が存在しないことを示す。

$n=1$ のとき、$a_1=1,\ b_1=0$ であるから、両方を割り切る素数は存在しない。

ここで、ある素数 $p$ が $a_{n+1}$ と $b_{n+1}$ をともに割り切ると仮定する。このとき

$$ p\mid b_{n+1}

$$

より、$b_{n+1}=a_n$ だから

$$ p\mid a_n

$$

である。また

$$ p\mid a_{n+1}

$$

であり、$a_{n+1}=2a_n+b_n$ だから

$$ p\mid 2a_n+b_n

$$

である。すでに $p\mid a_n$ なので、

$$ p\mid b_n

$$

も従う。

つまり、$p$ が $a_{n+1},b_{n+1}$ をともに割り切るならば、$p$ は $a_n,b_n$ もともに割り切る。

したがって、もしある $n$ で $a_n,b_n$ をともに割り切る素数 $p$ が存在するとすれば、この議論を繰り返して、最終的に $p$ は $a_1,b_1$ をともに割り切ることになる。しかし $a_1=1,\ b_1=0$ であるから、$p\mid a_1$ は成り立たない。

よって矛盾する。

したがって、任意の自然数 $n$ について、$a_n,b_n$ をともに割り切る素数は存在しない。

解法2

余りの係数の組をベクトルで表す。

$x^n$ の余りを $a_nx+b_n$ とすると、解法1と同様に

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

$$

である。これは

$$ \begin{pmatrix} a_{n+1}\\ b_{n+1} \end{pmatrix} =

\begin{pmatrix} 2&1\\ 1&0 \end{pmatrix} \begin{pmatrix} a_n\\ b_n \end{pmatrix}

$$

と書ける。

初期値は

$$ \begin{pmatrix} a_1\\ b_1 \end{pmatrix} =

\begin{pmatrix} 1\\ 0 \end{pmatrix}

$$

である。

行列

$$ M= \begin{pmatrix} 2&1\\ 1&0 \end{pmatrix}

$$

の行列式は

$$ \det M=2\cdot 0-1\cdot 1=-1

$$

である。したがって任意の素数 $p$ に対して、$M$ は $\bmod p$ で逆行列をもつ。

いま、ある素数 $p$ が $a_n,b_n$ をともに割り切ると仮定する。このとき

$$ \begin{pmatrix} a_n\\ b_n \end{pmatrix} \equiv \begin{pmatrix} 0\\ 0 \end{pmatrix} \pmod p

$$

である。

一方、

$$ \begin{pmatrix} a_n\\ b_n \end{pmatrix} =

M^{n-1} \begin{pmatrix} 1\\ 0 \end{pmatrix}

$$

であり、$M$ は $\bmod p$ で逆行列をもつので、両辺に $M^{-(n-1)}$ をかけることができる。すると

$$ \begin{pmatrix} 1\\ 0 \end{pmatrix} \equiv \begin{pmatrix} 0\\ 0 \end{pmatrix} \pmod p

$$

となる。

これは $1\equiv 0\pmod p$ を意味し、矛盾である。

よって、$a_n,b_n$ をともに割り切る素数は存在しない。

解説

この問題の中心は、割る多項式が

$$ x^2-2x-1

$$

であることから、余りの計算を

$$ x^2\equiv 2x+1

$$

という置き換えで処理する点である。

$x^n$ の余りを $a_nx+b_n$ とおくと、$x$ をかけるたびに係数が

$$ (a_n,b_n)\mapsto (2a_n+b_n,a_n)

$$

と更新される。この更新は整数係数だけで行われるため、$a_n,b_n$ が整数であることは自然に従う。

また、互いに素であることは、最大公約数を直接計算するよりも、「共通に割る素数があれば一つ前の段階にも戻れる」と見るのが本質である。漸化式が逆向きにも素数の割り切りを保存してしまうため、最終的に初期値 $(1,0)$ に矛盾する。

答え

すべての自然数 $n$ について、$x^n$ を $x^2-2x-1$ で割った余りを $a_nx+b_n$ とすると、$a_n,b_n$ は整数である。

さらに、$a_n,b_n$ をともに割り切る素数は存在しない。