名古屋大学 2004年度 前期日程 第2次学力試験 整数・数列理系数学 第4問(b)

次の2つの主張を同時に帰納法で示す。 $\text{(A)}{x}_n\text{ と }{x}_{n-1}\text{ は互いに素である},$ $\text{(B)}{x}_n\text{ と }b\text{ は互いに素である}\mathrm{.}$ $x_1=x_2=1$ であるから、$n=2$ ではどちらも成り立つ。

ある $n\geqq 2$ で、$x_n$ と $x_{n-1}$ が互いに素であり、かつ $x_n$ と $b$ が互いに素であると仮定する。まず $x_{n+1}$ と $b$ が互いに素であることを示す。$d$ を $x_{n+1}$ と $b$ の公約数とする。漸化式 $x_{n+1}=a{x}_n+b{x}_{n-1}$ より、$d$ は $b$ を割り、また $x_{n+1}$ を割るので、$d\mid a{x}_n$ である。ところが $a$ と $b$ は互いに素であり、$x_n$ と $b$ も互いに素である。$d$ は $b$ の約数だから、$d$ は $a$ とも $x_n$ とも互いに素である。よって $d=1$ である。したがって $x_{n+1}$ と $b$ は互いに素である。

次に $x_{n+1}$ と $x_n$ が互いに素であることを示す。$e$ を $x_{n+1}$ と $x_n$ の公約数とする。このとき $$e\mid x_{n+1}-a{x}_n=b{x}_{n-1}$$ である。一方、$e\mid x_n$ であり、仮定より $x_n$ と $x_{n-1}$ は互いに素であるから、$e$ と $x_{n-1}$ も互いに素である。したがって $e\mid b$ でなければならない。

しかし、上で示したように $x_{n+1}$ と $b$ は互いに素であり、$e$ は $x_{n+1}$ も割る。よって $e=1$ である。したがって $x_{n+1}$ と $x_n$ は互いに素である。

以上により、帰納法で任意の $n\geqq 1$ について $x_{n+1}$ と $x_n$ は互いに素である。

漸化式を法$b$で見ると$x_n$と$b$が互いに素であることが一度に分かる。その後、隣接2項の最大公約数を漸化式で1段ずつ前へ戻し、初期値まで降下させる。

漸化式を法$b$で見ると$$x_{n+1}\equiv a{x}_n(\mathrm{m}\mathrm{o}\mathrm{d}b)\mathrm{.}$$$x_2=1$だから、帰納的に$$x_n\equiv a^{n-2}(\mathrm{m}\mathrm{o}\mathrm{d}b)(n\geqq 2)$$である。$a$と$b$は互いに素なので$$\gcd (x_n,b)=1(n\geqq 2)$$を得る。

次に$n\geqq 2$について$$\begin{array}{rl}{\displaystyle \gcd (x_{n+1},x_n)}& {\displaystyle =\gcd (a{x}_n+b{x}_{n-1},x_n)}\\ {\displaystyle }& {\displaystyle =\gcd (b{x}_{n-1},x_n)\mathrm{.}}\end{array}$$$\gcd (b,x_n)=1$であるから$$\gcd (b{x}_{n-1},x_n)=\gcd (x_{n-1},x_n)\mathrm{.}$$よって同じ操作を繰り返せば$$\gcd (x_{n+1},x_n)=\gcd (x_n,x_{n-1})=\cdots =\gcd (x_2,x_1)=1.$$したがって、すべての正の整数$n$について
$x_{n+1}$と$x_n$は互いに素である。