プラチカ

プラチカIIICの10番なのですが

数列
ａn+1＝ａn+２ｂn
ｂn+1＝ａn＋ｂn


となるａnとｂnの最大公約数を出したいのですが、


解説には

ａnとｂnの最大公約数は |ａn^2－２ｂn^2|の約数である。


と書かれていました


なぜ最大公約数が上式の約数となるのか全くわかりません


わかるかた教えてください。お願いいたします。

No.1 ベストアンサー 回答者： rnakamra 回答日時： 2011/09/04 12:27

anとbnの最大公約数をkとすると

an=mk,bn=lk (m,lは整数)
とかけます。

|an^2-2bn^2|=|(mk)^2-2(lk)^2|=|m^2*k^2-2l^2*k^2|=|k^2*(m^2-2l^2)|=k^2*|m^2-2l^2|

となりますので|an^2-2bn^2|はkの倍数になります。

この回答へのお礼

ありがとうございました。


すごく分かりやすかったです！

お礼日時：2011/09/04 13:12