如何证明最大公因数(ma,mb)=最大公因数m(a,b)

问题描述:

如何证明最大公因数(ma,mb)=最大公因数m(a,b)

设m(a,b)=k,令a=ik,b=jk,则ma=mik,mb=mjk,mk=m(a,b)是ma,mb的一个公因数.假设ma,mb的最大公因数为c,且c>mk,ma=cd,mb=ce若c能被m整除,设c=lm,则有ma=lmd,mb=lme,a=ld,b=le,l是a,b的公约数,由假设c>mk,故lm>mk,l>k,与m...