欧几里德算法(辗转辗转相除法)所求的公约数为什么是最大公约数
来源:学生作业帮 编辑:作业帮 分类:数学作业 时间:2024/10/02 16:03:19
欧几里德算法(辗转辗转相除法)所求的公约数为什么是最大公约数
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).
定理得证.
欧几里德算法就是对照这个定理来做的,每一次辗转相除其实就是用了一次上面的定理,一步一步递推得到最后结果.
首先给定两个数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).
定理得证.
欧几里德算法就是对照这个定理来做的,每一次辗转相除其实就是用了一次上面的定理,一步一步递推得到最后结果.
辗转相除法最后的数字为什么一定是最大公约数?
欧几里德的辗转相除法中举了一个例子 例如,252和105的最大公约数是21(252 = 21 ×
辗转相除法为什么能求最大公约数
辗转相除法求最大公约数
高中VB程序题用辗转相除法求最大公约数.已知用辗转相除法求两个正整数m、n的最大公约数的算法如下:(用num1,num2
用辗转相除法求最大公约数.已知用辗转相除法求两个正整数m、n的最大公约数的算法如下:(用num1,num2,r
求两个数的最大公约数和最小公倍数,辗转相除法算法如何理解
用辗转相除法求最大公约数,为什么?理论依据?
求最大公约数与最小公倍数的辗转相除法的证明..
C语言 求最大公约数 辗转相除法的问题
,用“辗转相除法”求得459和357的最大公约数
用辗转相除法求两数的最小公倍数和最大公约数 VB