aとbをa=b=0でない２つの整数とする。a,bの公約数の集合の中の最

質問

aとbをa=b=0でない２つの整数とする。a,bの公約数の集合の中の最大数dを、aとbの最大公約数といい、
d=(a,b)とかく　例えば(6,4)=2　このときar+bs＝(a,b)のような整数rとsが存在するというのを証明する。という問題です、教えてください。

回答No.3

alice_44 · ベストアンサー

失礼、ミスプリがあった。
x[n+2] = x[n] - q[n]・x[n+1]・q[n] じゃなく、
x[n+2] = x[n] - q[n]・x[n+1] で、逆向きに漸化

(a,b) = x[m-1]
= x[m-3] - q[m-3]・x[m-2]
= x[m-3] - q[m-3]・{ x[m-4] - q[m-4]・x[m-3] }
= - q[m-3]・x[m-4] + { 1 + q[m-3]・q[m-4] }・x[m-3]
= - q[m-3]・x[m-4] + { 1 + q[m-3]・q[m-4] }・{ x[m-5] - q[m-5]・x[m-4] }
= { 1 + q[m-3]・q[m-4] }・x[m-5] - { q[m-3] + q[m-5] + q[m-3]・q[m-4]・q[m-5] }・x[m-4]
= { なんたら }・x[m-6] + { かんたら }・x[m-5]
= { ぺんたら }・x[m-7] + { ぽんたら }・x[m-6]
= …
= { いつかは }・x[0] + { こうなる }・x[1]
= { q[n] の整数係数多項式 }・a + { q[n] の整数係数多項式 }・b

q[n] はみな整数だから、その整数係数多項式の値も整数。

お礼

ありがとうございます。美しい解法に感動しました

回答No.2

alice_44

ユークリッドの互除法を行う。

x[0] = a,
x[1] = b,
x[n+2] = (x[n] を x[n+1] で割った余り)
で漸化すると、

x[m] = 0 となる m が存在し、x[m-1] = (a,b) である。

x[n] を x[n+1] で割ったときの、余りつきの商を q[n] と置くと、
x[n] = x[n+1]・q[n] + x[n+2] なので、

x[m-1] = (a,b) を初期値として、
x[n+2] = x[n] - q[n]・x[n+1]・q[n] で、逆向きに漸化してゆけば、
x[m-1] が x[0] と x[1] の整数係数一次式で表されることが解る。

補足

ありがとうございます、大変失礼とは思いますが当方、相当頭が悪くてまだ理解できません。

もう少し詳しく教えていただけないでしょうか(汗

回答No.1

Sinogi

>例えば(6,4)=2　このときar+bs＝(a,b)のような整数rとsが存在するというのを証明する。
a=6 b=4 とすると
6ｒ+4ｓ＝2　をみたす整数　ｒ/ｓを示せば証明が成立しますね

r=1
s=-1

で証明終了では？