欧几里得120、什么叫做辗转相除法？举几个例子

什么叫做辗转相除法？举几个例子——网友提问

…

2019-09-15，angela韩雪倩（qiàn）：辗转相除法最大的用途就是用来求两个数的最大公约数。

用（a，b）来表示a和b的最大公约数。有定理：已知a，b，c为正整数，若a除以b余c（a÷b=商……C），则（a，b）=（b，c）。（证明过程请参考其它资料）

…小学数学用“a÷b=商……C（a除以b余c）”表示有余数的除法…

…（a，b）=（b，c）：（被除数，除数）=（除数，余数）；被除数、除数的最大公约数=除数、余数的最大公约数…

…被除数、除数的最大公因数=除数、余数的最大公因数：例如，15、8的最大公因数为1，15除以8余7（15÷8=1……7），8、7的最大公因数是1，15、8的最大公因数=8、7的最大公因数=1…

2019-11-05，苗征宇发送视频。

视频内容：

“上个视频，我们学习了如何用分解质因数法求最大公因数和最小公倍数。在使用这个方法时，需要先将每个数分解质因数。例如90=2×3^2（90=2×3的平方），105=3×5×7…”主持人说。

“但并不是每个数都那么好分解。比如下面两个数就很难分解：3139=？2117=？…”主持人接着说。

“遇到这种情况，分解质因数法也无能为力，这怎么办？”主持人继续说。

“不用担心，这种情况就是辗转相除法大显身手的时刻…”主持人最后说。

“辗转相除法主要用来计算两个数的最大公因数。在使用时，先用较大的除以较小的，算出余数。然后用除数继续除以余数，求出新的余数。接着再用除数除以余数…不停循环…直到余数为0。”主持人说。

“此时的除数就是最大公因数。”主持人接着说。

“比方说这两个数：3139，2117…”主持人继续说，“首先用3139除以2117，商1，余1022。然后用除数2117除以1022，商2余73。接着继续用1022除以73，商14余0。余数为0，就此打住…”

“此时的除数73，就是3139和2117的最大公因数。”主持人最后说。

“无论两个数多大，用辗转相除法都可以方便的求出最大公因数。是不是很厉害！”主持人说。

“这个方法，大家以后在学计算机编程的时候还会见到。到时，你可以让电脑快速计算最大公因数。是不是很帅！”主持人最后说。

2020-07-12，183*****858：除数除以余数得0后，除数就是最大公因数。

辗转相除法，其计算原理依赖于下面的定理：

…辗、转、辗转、辗转相除法：见《欧几里得119》…

…原、理、原理：见《欧几里得41》…

…定、理、定理：见《欧几里得2》…

定理：两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数。

…其它表述为：被除数、除数、余数是整数，被除数除以除数，得到余数，则（被除数，除数）=（除数，余数）；a、b、c是整数，a除以b余c，则（a，b）=（b，c）；a、b、c是整数，a÷b=商……c，则（a，b）=（b，c）…

[…（a，b）：整数a与整数b的最大公约数…]

“a、b、c是整数，a÷b=商……c，则（a，b）=（b，c）”有多种证法：

证法一

a可以表示成a = kb + r（a，b，k，r皆为正整数，且r），则r = a mod b

…mod：“Module Operation”的首字母缩写（取前三个字母）…

…module（英语）：n.（名词）单元（尤指英国大学课程的一部分）；模块；功能块；程序块；组件；配件…

…Operation（英语）：n.操作；经营；[外科]手术；[数][计]运算…

（…[数]：数学行业…

…[计]：计算机行业…）

…Module Operation：取模运算…

“取模运算是求两个数相除的余数。

请看下集《欧几里得121、取、模，运、算、运算，取模运算》”

若不知晓历史，便看不清未来

欢迎关注博客"人性的游戏"或微博"人性的游戏"