Question

ぽちゃこ

ユーグリット互除法って、どうして成り立つんですか？
すみません、自分で調べてみたのですがよく分からなくて💦

Answer 1

✨ คำตอบที่ดีที่สุด ✨

Take

クロワッサンさま
以下、a , b の最大公約数を記号 (a,b) で表す。(a≧b とする)
次の①を認めれば、①を繰り返すことで
a÷b=q1…r1　⇔　(a,b)=(b,r1)　…①
b÷r1=q2…r2　⇔　(b,r1)=(r1,r2)
r1÷r2=q3…r3　⇔　(r1,r2)=(r2,r3)
…
rn-2÷rn-1=qn…rn　⇔　(rn-2,rn-1)=(rn-1,rn)
rn-1÷rn=qn+1…0　⇔　(rn-1,rn)=rn
∴(a,b)=(b,r1)=(r1,r2)=…=rn
となり、Euclidの互除法の証明は終わる。あとは①の証明だが、
a÷b=q1…r1　⇔　a=bq1+r1　…(☆)
(ⅰ)a,bの公約数をdとすると
a=a'd , b=b'd　
これと(☆)より
r1=a-bq1=a'd-b'dq1=(a'-b'q1)d
　　
(ⅱ)

(a,b)=(b,r1)　…①

Take

ごめんなさい。つづきです。
(ⅰ)a,bの公約数をdとすると
a=a'd , b=b'd　
これと(☆)より
r1=a-bq1=a'd-b'dq1=(a'-b'q1)d
よって、dはbとr1の公約数。
(ⅱ)b,r1の公約数をeとすると
b=b''e , r1=r'e　
これと(☆)より
a=bq1+r1=b''eq1+r'e=(b''q1+r')e
よって、eはaとbの公約数。
(ⅰ)(ⅱ)より公約数の全体が一致するから、最大公約数も一致する。
∴(a,b)=(b,r1)　…①
が成り立ち、証明が完成する。　■

ぽちゃこ

ありがとうございます！頑張ってりかいします！