数论证明。求高手教

来源：百度知道 编辑：UC知道 时间：2024/06/14 07:30:41
有整数a，b，q，r使得a=bq+r，0≤r＜b。即q为b除a的商，r为b除a的余数。
试证：(a,b)=(b,r) ，即被除数与除数的最大公约数等于除数与余数的最大公约数。

因为a=bq+r,所以,a与b的任一公因子必能整除r,所以d=(a,b)也是b与r的公因子,所以(a,b)<=(b,r);
又r与b的公因子也能整除a,所以(b,r) | (a,b)
所以(b,r) <=(a,b);
综上:(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, 矛盾
所以命题成立