陥没地帯 (19) - ノリの悪い日記

クサキョウチクトウ (オイランソウ)。まだ咲き始めだなあ。

f:id:noriharu-katakura:20201104101338j:plain

【問】
$n$ は正の整数とする。 $x^{n+1}$ を $x^2 - x - 1$ で割った余りを $a_{n}x + b_{n}$ とおく。

$\text{(1)}$
数列 $a_{n}, b_{n}, n = 1, 2, 3, \cdots$ は

$a_{n+1} = a_{n} + b_{n}$
$b_{n+1} = a_{n}$

を満たすことを示せ。

$\text{(2)}$
$n = 1, 2, 3, \cdots$ に対して、 $a_{n}, b_{n}$ はともに正の整数で、互いに素であることを証明せよ。

【解】
$\text{(1)}$
$x^{n+1} = F(x)(x^2-x-1)+a_{n}x+b_{n}$

とおくと、

$x^{n+2} \\ \begin{align} &= x\cdot x^{n+1}\\&= xF(x)(x^2-x-1)+a_{n}x^2+b_{n}x \\ &=(xF(x)+a_{n})(x^2-x-1) \\ & +(a_{n}+b_{n})x+a_{n} \end{align}$

したがって、

$a_{n+1} = a_{n} + b_{n}$
$b_{n+1} = a_{n}$

である。

$\text{(2)}$

$a_{n}, b_{n}$ がともに正の整数であること:

$x^2=1 \cdot (x^2 - x - 1) + x + 1$

から、

$a_{1} = b_{1} = 1$

は正の整数である。 $k \gt 1$ の正の整数について、帰納法の仮定を使って $a_{k} , b_{k}$ を正の整数だとすると、 $\text{(1)}$ の

$a_{k+1} = a_{k} + b_{k}$
$b_{k+1} = a_{k}$

から、 $a_{k+1} , b_{k+1}$ も正の整数である。

$a_{n}, b_{n}$ が互いに素であること:

$a_{1}=1 , b_{1}=1$ の最大公約数は $1$ だから $a_{1} , b_{1}$ は互いに素である。

$k \gt 1$ の正の整数について、帰納法の仮定を使って $a_{k} , b_{k}$ は互いに素だとする。

まず、 $a_{k+1} , b_{k+1}$ の最大公約数は、 $b_{k}, b_{k+1}$ の最大公約数に等しい。このことを以下に証明する。

(以下、証明)
$\text{(1)}$ から、

$a_{k+1} - b_{k+1} = b_{k}$

であるが、任意の $b_{k}, b_{k+1}$ の公約数は $a_{k+1}$ も割り切るので $a_{k+1}$ と $b_{k+1}$ の公約数である。逆に任意の $a_{k+1} , b_{k+1}$ の公約数は $b_{k}$ も割り切るので、 $b_{k}$ と $b_{k+1}$ の公約数である。したがって $a_{k+1} , b_{k+1}$ の公約数全体の集合は、 $b_{k}, b_{k+1}$ の公約数全体の集合と等しく、したがって最大公約数も等しい。
(以上証明終わり)

ところが、 $b_{k}, b_{k+1}$ の最大公約数は $1$ である。このことを以下に証明する。

(以下証明)
$\text{(1)}$ から、

$b_{k+1} - b_{k} = a_{k} - b_{k}$

なので、 $b_{k}, b_{k+1}$ の任意の公約数 $d$ は、 $a_{k} - b_{k}$ を割り切る。 $b_{k}$ は $d$ で割り切れるので、 $a_{k}$ も $d$ で割り切れる。いま、 $d \gt 1$ と仮定すると、 $a_{k} , b_{k}$ の最大公約数が $1$ であることに矛盾する。したがって、 $b_{k}, b_{k+1}$ の最大公約数は $1$ である。
(以上証明終わり)

$a_{k+1} , b_{k+1}$ の最大公約数は、
$b_{k} , b_{k+1}$ の最大公約数に等しく、 $1$ である。//