数论证明.有整数a,b,q,r使得a=bq+r,0≤r＜b.即q为b除a的商,r为b除a的余数.试证：(a,b)=(b,r) ,即被除数与除数的最大公约数等于除数与余数的最大公约数.

仅说一下自己的想法 不一定是最好的方法
用反证法 设(a,b)=m,(b,r)=n 若m与n不相等则(m,n)=d,
令n=de,则(m,e)=1,a=m*x,b=m*e*y, r=d*e*z,
mx=meyq+dez,可知 由于(m,e)=1,所以e|x,
但(a,b)=me, 推出矛盾 则m=n
若(m,n)=n, ex=eyq+z,e|z,(b,r)=m, 矛盾
若(m,n)=m, x=eyq+ez,e|x,(a,b)=n, 矛盾
所以命题成立

因为a=bq+r,所以,a与b的任一公因子必能整除r,所以d=(a,b)也是b与r的公因子,所以(a,b)