トップ› 基礎問題› 数学B› 数列› 漸化式の応用› 問題 3

数学B 漸化式の応用問題 3 解説

方針・初手

$x^2$ を $x^2-6x-12$ で割った余りは、合同式

$$ x^2 \equiv 6x+12 \pmod{x^2-6x-12} $$

として扱うとよい。

$x^n$ の余りを $a_nx+b_n$ とおき、両辺に $x$ を掛けて $x^{n+1}$ の余りを求めることで、$a_n,b_n$ の漸化式が得られる。

解法1

まず

$$ x^2=(x^2-6x-12)+(6x+12) $$

であるから、$x^2$ を $x^2-6x-12$ で割った余りは $6x+12$ である。

したがって

$$ a_2=6,\qquad b_2=12 $$

である。

次に、$x^n$ を $x^2-6x-12$ で割った余りが $a_nx+b_n$ であるから、

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

である。両辺に $x$ を掛けると

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

となる。

ここで

$$ x^2 \equiv 6x+12 \pmod{x^2-6x-12} $$

を用いると、

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

である。

よって

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

を得る。

最後に、$a_n,b_n$ の公約数で素数となるものを調べる。

まず $a_2=6,b_2=12$ はどちらも $2,3$ で割り切れる。さらに、$a_n,b_n$ がともに $2,3$ で割り切れるとすると、

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

より、$a_{n+1},b_{n+1}$ もともに $2,3$ で割り切れる。

したがって、数学的帰納法により、すべての $n\geqq 2$ に対して $2,3$ は $a_n,b_n$ の公約数である。

次に、$2,3$ 以外の素数が公約数にならないことを示す。

漸化式を行列で書くと

$$ \begin{pmatrix} a_{n+1}\\ b_{n+1} \end{pmatrix} = \begin{pmatrix} 6&1\\ 12&0 \end{pmatrix} \begin{pmatrix} a_n\\ b_n \end{pmatrix} $$

である。ここで

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

とおくと、

$$ \det M=-12 $$

である。

$p$ を $2,3$ 以外の素数とする。このとき $p$ は $12$ を割らないので、

$$ \det M=-12 \not\equiv 0 \pmod p $$

であり、$M$ は法 $p$ で逆行列をもつ。

もしある $n$ に対して $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-2} \begin{pmatrix} a_2\\ b_2 \end{pmatrix} $$

であり、$M$ は法 $p$ で逆行列をもつから、

$$ \begin{pmatrix} a_2\\ b_2 \end{pmatrix} \equiv \begin{pmatrix} 0\\ 0 \end{pmatrix} \pmod p $$

が従う。

しかし

$$ \begin{pmatrix} a_2\\ b_2 \end{pmatrix} = \begin{pmatrix} 6\\ 12 \end{pmatrix} $$

であり、$p$ は $2,3$ 以外の素数なので、$6,12$ をともに割ることはない。これは矛盾である。

したがって、$a_n,b_n$ の公約数で素数となるものは、すべての $n\geqq 2$ に対して $2,3$ のみである。

解説

余りを扱う問題では、割る式から得られる関係

$$ x^2 \equiv 6x+12 $$

を使って次数を下げるのが基本である。

(2) は、$x^n$ の余りに $x$ を掛けてから、$x^2$ を $6x+12$ に置き換えるだけでよい。

(3) では、$2,3$ が常に公約数であることは漸化式から直接わかる。一方で、$2,3$ 以外の素数を排除するには、漸化式を行列で見て、行列式が $-12$ であることを使うのが簡潔である。$p\neq 2,3$ ならこの行列は法 $p$ で可逆なので、途中で両成分が $0$ になるなら初期値も両成分が $0$ でなければならない。しかし初期値 $(6,12)$ はそのような素数では同時に割り切れない。