辗转相除法

用了很久但没证明过,现在试下.... a = bq+r 其中(a,b,q>0 0<r<b) (a,b) 为求其最大公因数 b|a   b整除a. 1.假设(a,b)=d d>0  m,n为正整数 a=dm  ,  b=dn r=a-bq=dm-dnq=d(m-nq) 所以 d|r  d|b d<=(r,b) 设(r,b)=D 所以  D>=d 2.  D|b,D|r, 又a=bq+r  所以 D|a D|b  -> D|(a,b)  又以为(a,b)=b -> D<=b 综合1,2所以D=b 得证