为什么除数和余数的最大公约数就是被除数和除数的最大公约数?(一直想不通,要求详细解说!!!)

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

设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)。

这个可以用反证法证明。我试着证明一下。 设被除数a，除数b，商c，余数d，a、b的最大公约数是e，a、b、c、d、e都是整数 那么有a÷b=c…………d。这样可以得到等式a=b×c+d 那么因为e是a、b的公约数，所以e是a和b的约数，因为a是e的倍数，b是e的倍数，那么b×c也是e的倍数，这样d=a-b×c是两个e的倍数相减，所以也是e的倍数。因此e也是b、d的公约数。 再证明e是b、d的最大公约数。用反证法。 设还有一个数x>e也是b、d的公约数。那么a=b×c+d也是x的倍数，那么x也是a、b的公约数，因为x>e，这与e是a、b的最大公约数的设定矛盾，这说明不存在比e更大的b、d的公约数，所以e就是b、d的最大公约数。