欢迎来到天天文库
浏览记录
ID：51529947
大小：20.00 KB
页数：1页
时间：2020-03-12
《更相减损术原理.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、更相减损术的原理：(a,b)=(a-b,b)这里将gcd(a,b)简记为(a,b).更相减损术是辗转相除法（欧几里德算法，Euclidalgorithm）的一个特例，它的原理是(a,b)=(a-nb,b)下面我们来证明：(a,b)=(a-nb,b)证：不妨设d是a,b的最大公因子。即a=rd,b=sd,并且其中(r,s)=1,即存在x,y,使得xr+ys=1.从而a-nb=(r-ns)d,b=sd,且x(r-ns)+(xn+y)s=xr+ys=1,即(r-ns,s)=1于是:d=(a-nb,b)于是得证。
此文档下载收益归作者所有
