为什么除数和余数的最大公约数就是被除数和除数的最大公约数?(一直想不通,)算法我懂,就是不懂这一个细节

Question

为什么除数和余数的最大公约数就是被除数和除数的最大公约数?(一直想不通,)
算法我懂,就是不懂这一个细节

Answer 1

设a、b为正整数,且a＞b,a=bq＋r,q、r也为正整数,且0＜r＜b；这里,a为被除数、b为除数、q为商、r为余数；设a与b的最大公约数为d,即(a,b)=d,试证(b,r)=(a,b)=d；证明:由于(a,b)=d,所以可设a=md、b=nd,m、n为正整数,且(m,n)=1；r=a-qb=md-qnd=d(m-qn),所以d能整除r,即d|r；由于d|b,所以d|(b,r)①；假设(b,r)=D＞d②,则D|(bq＋r),即D|a,所以D|(a,b),所以D≦(a,b),即D≦d,这和②矛盾!结合①可知(b,r)=d,即(b,r)=(a,b).