フィボナッチ数列の性質9

中学受験専門塾・優学習会 すぐるホームページ > すぐるゼミ > 算数 > フィボナッチ数列と中学入試問題 > フィボナッチ数列の性質9
 性質9   FmとFnの最大公約数 = Fmとnの最大公約数
 まず,性質9の証明のために,次の補題1を証明します。(リンクをクリックすると証明ページに移動します。)
 補題1   m を n で割ったときのあまりを r とすると,FmとFnの最大公約数 = FnとFrの最大公約数
 また,性質9の証明のためには,次の「ユークリッドの互除法」による最大公約数の求め方が必要です。
 ユークリッドの互除法
 m を n で割ったときのあまりを r1 とする。
 n を r1 で割ったときのあまりを r2 とする。
 r1 を r2 で割ったときのあまりを r3 とする。
 ………………………………

 以上の処理を続けていくと,いつか次のようになる。

 rk-1 を rk で割ると割り切れる。

 このとき,m と n の最大公約数は,rk になる。
 この「ユークリッドの互除法」に,補題1を追加して書いてみると,うまい具合に関連づけられることがわかります。

 ユークリッドの互除法(補題1の追加版)
 m を n で割ったときのあまりを r1 とすると,  FmとFnの最大公約数 = FnとFr1の最大公約数
 n を r1 で割ったときのあまりを r2 とすると,  FnとFr1の最大公約数 = Fr1とFr2の最大公約数
 r1 を r2 で割ったときのあまりを r3 とすると,  Fr1とFr2の最大公約数 = Fr2とFr3の最大公約数
 ………………………………  ………………………………

 以上の処理を続けていくと,いつか次のようになる。

 rk-1 を rk で割ると割り切れる。このとき,性質7により,Frk-1 は Frk で割り切れる。よって,Frk-1 と Frk の最大公約数は Frk になる。
 よって,m と n の最大公約数は,rk になる。 したがって,FmとFnの最大公約数 = Frk
 上のユークリッドの互除法(補題1の追加版)において,性質7とは,
 性質7   nがmで割り切れるならば,FnはFmで割り切れる
 という性質でした。

 以上のことから,FmとFnの最大公約数 = Frk = Fmとnの最大公約数 となり,性質9が証明されました。
(証明終わり)  

Copyright (C) 1996- Suguru Corporation. All Rights Reserved.