整数a,b,最大公因数是d,则存在整数m,n使得am+bn=d.网上看到的定理,原证明过程不详细没看懂,求这个定理的详细证明过程,就算是错的也请证明,不要出现例如辗转相除法,最后回带即可之类的语言

Question

整数a,b,最大公因数是d,则存在整数m,n使得am+bn=d.
网上看到的定理,原证明过程不详细没看懂,求这个定理的详细证明过程,就算是错的也请证明,不要出现例如辗转相除法,最后回带即可之类的语言.只给我能看懂的人分

Answer 1

根据已知,可知存在互素的整数s和t,使得a=sd,b=td
如果s与t不互素,则存在最大公约数g,使得h|s,h|t,d就不是a与b的最大公因数,与已知矛盾.
存在整数m,n使得am+bn=sdm+tdn=(ms+nt)d=d,即
ms+nt=1
其中s与t互素,是此公式成立的充要条件,可以证明如下：
必要性：ms+nt=1成立,则s,t互素,因为这时存在s,t的公因子g使得g|ms+nt=1,g=±1
充分性：假定s,t互素,不妨设s与t都是正整数,对s与t做归纳.
存在整数q,r使s=qt+r 且0≤r＜t.如果r=0,则t|s,但因s,t互素,故t=1,当然存在m,n使ms+nt=1.如果r≠0,则t,r互素.由归纳存在整数m1,n1使m1t+n1r=1,于是n1s=n1qt+n1r=n1qt+1-m1t.因此n1s+(m1-n1q)t=1,定理得证.