公約数で

質問

解答をみていてちょっと分らない部分があったのでご質問させていただきます。(表記しづらいので、数列Anで第n+1項を A(n+1)と表します)分らないのは、帰納法での証明の一部分です。また【　】の中は前問で証明されていたり条件として成り立っているとします。

【A(n+1) = An+Bn , B(n+1) = An … (1)　
　An,Bnは自然数で互いに素 … (2) 】

(1)、(2)からA(n+1)とB(n+1)は自然数である。
ここでA(n+1)とB(n+1)が互いに素でないとすると、
A(n+1)とB(n+1)は１より大きい公約数ｒを持つ。
___＿__＿_________________(ここまでは分ります)

(1)より Bn ＝ A(n+1)－An
であるからｒはＢnの約数でもありｒはAnとBn
の１より大きい公約数である。
＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿
この部分が分りません＾＾；どうしてｒはＢnの約数でもありｒはAnとBnの１より大きい公約数であるのでしょうか？分る方お願いします。

回答No.1

eatern27 · ベストアンサー

＞A(n+1)とB(n+1)は１より大きい公約数ｒを持つ。
ここから
A(n)=B(n+1)もrの倍数です。

つまり、A(n+1)もA(n)もrの倍数です。

よって、
＞Bn ＝ A(n+1)－An
の右辺はｒの倍数からｒの倍数を引いたものなので、全体もｒの倍数。
つまり、B(n)もrの倍数である事が分かります。

A(n),B(n)はどちらもrの倍数である事が分かりましたから、rはA(n),B(n)の公約数です。rは1より大きいと仮定していたので、

＞ｒはＢnの約数でもありｒはAnとBnの１より大きい公約数である。

となります。

言葉で説明しましたが、
A(n+1)=r*a(n+1),B(n+1)=r*b(n+1)などとけば、分かりやすいと思います。