ノリの悪い日記

古今東西の映画、ポピュラー音楽、その他をいまここに交錯させながら随想します。

陥没地帯 (19)

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

f:id:noriharu-katakura:20200623112351j: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 である。//