欧几里德算法(辗转辗转相除法)所求的公约数为什么是最大公约数RT,我只知道最后的得数一定是两者的公约

欧几里德算法(辗转辗转相除法)所求的公约数为什么是最大公约数RT,我只知道最后的得数一定是两者的公约

这个不难,去翻翻《近世代数》,《数论》,这种书上都有的,我在此稍微写一下,：首先给定两个数a,b（a>b）,则根据除法运算,a/b=q.r.q是商,r是余数.也可以表示为a=bq+r.这是小学就知道的.下面给出一个定理：若a=bq+r,则（a,b）=（b,r）,即a,b的最大公约数等于b,r的最大公约数.举个例子来说：24=10*2+4,那么(24,10)=(10,4)=2这个定理的证明也很简单.设c是a和b的任意一个公约数,则c能同时整除a和b,即a=cx,b=cy,（x,y是整数）将它们代入“a=bq+r”中：cx=cyq+r得到r=c(x-yq),说明c也能整除r,即c也是b和r的公约数.于是a和b的公约数就是b和r的公约数,那么a和b最大公约数就是b和r的最大公约数,（a,b）=（b,r）.定理得证.欧几里德算法就是对照这个定理来做的,每一次辗转相除其实就是用了一次上面的定理,一步一步递推得到最后结果.

正好我需要