ここでは多項式 $x^n$ を $x$ の2次式で割った余りの係数の公約数に関する問題を説明します。
単に $x$ の多項式を2次式で割った余りを求める問題なら，得意な人もいるかもしれません。
しかし今回扱う問題のように，漸化式を立式させる問題や「素数」という文字を見た瞬間，「これ絶対ダメな問題だわ～」と思ってしまう人もいるでしょう。
見た瞬間に解けないと思うほど苦手な問題でも，実はそれほど難しくない問題もあります。
この記事によって，苦手な問題が少なくなる人がいることを期待します。
2007年 東北大
それでは次の問題を解いてみよう。
(1) $a_2,~b_2$ を求めよ。
(2) $a_{n+1},~b_{n+1}$ を $a_n,~b_n$ を用いて表せ。
(3) 各 $n$ に対して，$a_n$ と $b_n$ の公約数で素数となるものをすべて求めよ。
(1)の考え方と解答
最初は $a_2,~b_2$ を求める問題。
2次式を2次式で割るだけだから一瞬で求められるはず。
$x^2$ を $x^2-6x-12$ で割ると
x^2=(x^2-6x-12)\Cdota1+6x+12
\end{align*}
a_2=6,~b_2=12
\end{align*}
(2)の考え方と解答
(2) $a_{n+1},~b_{n+1}$ を $a_n,~b_n$ を用いて表せ。
まず $a_n,~b_n$ の意味について整理しておこう。
$x^n$ を $x^2-6x-12$ で割ったときの商を $Q_n(x)$ とおくと，余りが $a_nx+b_n$ であるから，
x^n=(x^2-6x-12)Q_n(x)+a_nx+b_n~\cdots\cdots①
\end{align*}
また同様に考えると $x^{n+1}$ を $x^2-6x-12$ で割ったときの商は $Q_{n+1}(x)$ とおくことができ，余りが $a_{n+1}x+b_{n+1}$ であるから
x^{n+1}=(x^2-6x-12)Q_{n+1}(x)+a_{n+1}x+b_{n+1}~\cdots\cdots②
\end{align*}
$a_{n+1},~b_{n+1}$ と $a_n,~b_n$ の関係式を求めるために，①と②の違いに着目しよう。
と言っても，$x^n$ と $x^{n+1}$ くらいしか考えるところがない気がする。
では $x^n$ をどうすれば $x^{n+1}$ に変えることができるだろうか？
次数が1つ上がっているね。今回の場合，最も簡単に次数を挙げるためには両辺に $x$ をかければ良いね。
①の両辺に $x$ をかけると
x^{n+1}=(x^2-6x-12)xQ_n(x)+a_nx^2+b_nx
\end{align*}
2次式で割っているから余りは1次式または定数だからね。
つまり，$a_nx^2+b_nx$ を $x^2-6x-12$ で割った余りが，$x^{n+1}$ を $x^2-6x-12$ で割った余りになる。
ここまでを理解することができれば，あとは計算するだけだね。
$x^n$ を $x^2-6x-12$ で割ったときの商を $Q_n(x)$ とおくと，余りが $a_nx+b_n$ であるから，
x^n=(x^2-6x-12)Q_n(x)+a_nx+b_n~\cdots\cdots①
\end{align*}
x^{n+1}&=(x^2-6x-12)xQ_n(x)+a_nx^2+b_nx \\[4pt]
&=(x^2-6x-12)xQ_n(x)+a_n(x^2-6x-12)+(6a_n+b_n)x+12a_n \\[4pt]
&=(x^2-6x-12)\left(xf(x)+a_n\right)+(6a_n+b_n)x+12a_n
\end{align*}
a_{n+1}=6a_n+b_n,~b_{n+1}=12a_n
\end{align*}
(3)の考え方と解答
(3) 各 $n$ に対して，$a_n$ と $b_n$ の公約数で素数となるものをすべて求めよ。
$n=2$ のときは $a_2=6$ と $b_2=12$ の公約数で素数となるものは2と3とすぐに分かるね。
今回問題なのは「各 $n$ に対して」という部分。
すべての $n$ の値に対して求めるものが2と3になるかは分からないね。
$n$ の値によっては，$a_n$ と $b_n$ の公約数で素数となるものが2と3以外にあるかもしれない。
その部分をどのようにして調べるかがポイントとなるね。
ということで実験してみよう。
(2)で求めた漸化式で $n=2$ とすると
a_3&=6a_2+b_2 \\[4pt]&=6\Cdota6+12 \\[4pt]&=48=2^6\Cdota3 \\[4pt]b_3&=12a_2 \\[4pt]&=12\Cdota6 \\[4pt]&=72=2^3\Cdota3^2
\end{align*}
たった1組しか計算していないが，やっぱり答えは2と3だけなのかもしれないと思うはず。
それならば，そのことを証明しなければいけないね。
$a_2,~a_3,~b_2,~b_3$ の素因数が2と3以外にないことに着目しよう。
実際 $a_n$ の素因数が2と3以外になければ $b_{n+1}=12a_n$ より，$b_{n+1}$ の素因数も2と3以外にないことになる。
しかし $n$ が増える方向で話を進めると終わりが見えないから，一般的には説明するのが難しく感じると思う。
そこで $n$ が減る方向で話を進めると，最後は $n=2$ に落ち着くから終わりがあって説明しやすい。
また「○○しか存在しない」という証明も一般的には難しいので，「○○以外のものがあるとしたら矛盾が生じる」という背理法を利用することで説明しやすくなる。
ということで，$a_n$ と $b_n$ の公約数で素数のものが2と3以外に存在するとして話を進めよう。
$a_2=6,~b_2=12$ の公約数で素数であるものは，$2,~3$ である。
$a_{n+1}$ と $b_{n+1}$ が $2,~3$ 以外の素数 $p$ を公約数にもつと仮定すると，$b_{n+1}=6a_n$ より $a_n$ も $p$ を約数にもつことになる。
また $a_{n+1}=6a_n+b_n$ より
b_n=a_{n+1}-6a_n
\end{align*}
これを繰り返すことによって，$a_2,~b_2$ も $p$ を公約数にもつことになるが，$p$ が $2,~3$ 以外であることに反する。
よって，このような $p$ は存在せず，2以上の整数 $n$ に対して $a_n,~b_n$ の公約数で素数となるものは2と3のみである。