为什么被除数和除数的最大公约数就是除数和余数的最大公约数我要的是解释,算法我会

题目详情

为什么被除数和除数的最大公约数就是除数和余数的最大公约数
我要的是解释,算法我会

▼优质解答

答案和解析

这个可以用反证法证明.我试着证明一下.
设被除数a,除数b,商c,余数d,a、b的最大公约数是e,a、b、c、d、e都是整数
那么有a÷b=c…………d.这样可以得到等式a=b×c+d
那么因为e是a、b的公约数,所以e是a和b的约数,因为a是e的倍数,b是e的倍数,那么b×c也是e的倍数,这样d=a-b×c是两个e的倍数相减,所以也是e的倍数.因此e也是b、d的公约数.
再证明e是b、d的最大公约数.用反证法.
设还有一个数x>e也是b、d的公约数.那么a=b×c+d也是x的倍数,那么x也是a、b的公约数,因为x>e,这与e是a、b的最大公约数的设定矛盾,这说明不存在比e更大的b、d的公约数,所以e就是b、d的最大公约数.

看了为什么被除数和除数的最大公约...的网友还看了以下：

关于最小公倍数.32和48的公倍数是（）.按照最小公倍数的公式,两数成互质关系,最小公倍数就是关于　2020-06-05 …

一道数学题：求各组最小公倍数：（要连乘的算式）2、3和4的最小公倍数10、12和24的最小公倍数1 　2020-06-13 …

最大公因数5和118和95和8他们的公因数是多少?从这些数中你发现了什么(有关公因数的)5和11的　2020-07-18 …

已知某数与24的最大公约数为4,最小公倍数为168,求此数.已知两个自然数的最大公约数为4,最小公　2020-07-18 …

求出下面每组数的最大公因数,并说一说他们的公因数还有哪些?回答正确加悬赏.（1）25和75最大公因　2020-07-31 …

3A-2AB+4B是几次几项式?2/3*XY-0.25的项和次数是?A^2+2A^2*B+AB^2 　2020-08-01 …

21和28的最大公倍数,16和28,32和24,27和54,3''8和12所有最小公倍数和最大公21 　2020-11-24 …

最小公倍数和最大公因数!~!~急一.直接写出下面每组两个数的最小公倍数32和66最小公倍数27和9最　2020-11-24 …

最小公倍数和最大公因数1.8和24的最小公倍数：最大公因数：2.63和18的最小公倍数：最大公因数：　2020-11-24 …