https://spherical-harmonics.hateblo.jp/entry/Kyodai/2013/Rikei

2025.05.10記

[3] $n$ を自然数とし，整式 $x^n$ を整式 $x^2-2x-1$ で割った余りを $ax+b$ とする．このとき $a$ と $b$ は整数であり，さらにそれらをともに割り切る素数は存在しないことを示せ．

本問のテーマ

2025.05.22記
余りを考える割り算とは引けるだけ引く引き算のことなので整数係数の多項式を整数係数で割った商も余りも整数係数となることはアタリマエすぎるので，これを示せと言われると困る気もするが，筆算をイメージすると整数の加減乗を用いて帰納的に次数下げが実現できていることに着目する．なお本問は誘導なしで出題されるぐらい有名な問題になってしまった感がある．

なお，この手の問題だと $a$ と $b$ が互いに素であることを示せとなるところだが， $n=1$ のときに $b=0$ となるので「互いに素」や「最大公約数」という言葉を避けて「それらをともに割り切る素数」という言葉を選んだのだろうなと思う．

[解答]
$n$ を自然数とし，整式 $x^n$ を整式 $x^2-2x-1$ で割った商を $P_n(x)$ ，余りを $a_n x+b_n$ とする．このとき
$x^n=(x^2-2x-1)P_n(x)+a_n x+b_n$
から
$x^{n+1}=(x^2-2x-1)xP_n(x)+a_n x^2+b_n x$ $=(x^2-2x-1)(xP_k(x)+a_k)+(2a_n+b_n) x+a_n$
が導けるので， $x=(x^2-2x-1)\cdot 0+1x+0$ とから連立漸化式 $a_1=1$ ， $b_1=0$ ， $a_{n+1}=2a_n+b_n$ ， $b_{n+1}=a_n$ が成立する．

よって $a_n$ ， $b_n$ は漸化式から整数列となることがわかる．

また， $n=1$ のとき $a_1=1$ ， $b_1=0$ をともに割り切る素数はなく， $n\geqq 2$ に対して $a_n$ と $b_n$ がともに素数 $p$ で割り切れると仮定すると $a_{n-1}=b_n$ ， $b_{n-1}=a_n-2b_n$ がともに素数 $p$ で割り切れることとなり，帰納的に $a_1=1$ が素数 $p$ で割り切れることとなり矛盾する．よって題意は示された．

通常，ユークリッドの互除法により $\gcd (a_{n}，b_{n})$ $=\gcd (2a_{n-1}+b_{n-1}，a_{n-1})$ $=\gcd (b_{n-1}，a_{n-1})$ を示して帰納的に $\gcd (a_{n}，b_{n})$ $=\gcd (a_{1}，b_{1})$ $=\gcd (1，0)=1$ が成り立つので $a_{n}$ と $b_n$ は互いに素となることを用いる訳だが，その際に用いる $=\gcd (n，0)=0$ については高校ではきちんと定義されていないようなので，それを避けた解答となっている．

本問の場合， $\{a_n\}$ ， $\{b_n\}$ は単調増加（証明は帰納法）であるから $a_2，b_2\geqq 1$ となり $\gcd (a_{n}，b_{n})$ $=\gcd (a_2，b_2)$ $=\gcd (2，1)=1$ を示す際に $0$ が登場しないことがわかるのだが，一手余計になってしまう．

2013年(平成25年)京都大学-数学(文系)[3] - [別館]球面倶楽部零八式markIISR
の類題．