欧几里得95、欧几里得算法（辗转相除算法）2

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

“但并不是每个数都那么好分解…比如这两个数就很难分解：3139=？2117=？…”网友接着说。

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

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

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

“此时的除数就是最大公因数…”网友接着说。

…

求（大数，小数）

…（a，b）：在数论中，记法（a，b）表示整数a与整数b的最大公约数（greatest common divisor，也译作最大公因数），即所有能同时整除 a 与 b 的正整数中最大的那一个…

大数÷小数=商…余A

      小数÷A=商…余B

            A÷B=商…余C

                    …

                   被除数÷除数=商…余0

此时除数就是最大公因数。

…

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

“此时的除数73，就是3139和2117的最大公因数…”网友最后说。

…

求（3139，2117）

3139÷2117=1……余1022

      2117÷1022=2……余73

        1022÷73=14……余0

73就是3139和2117的最大公因数。

…

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

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

…

“辗转相除法最大的用途就是用来求两个数的最大公约数。用（a，b）来表示a和b的最大公约数。有定理：已知a，b，c为正整数，若a除以b余c（a÷b=商……C），则（a，b）=（b，c）…”网友angela韩雪倩说。

“证明过程请参考其它资料…”Angela韩雪倩接着说。

…angela韩雪倩：百度问答用户…Angela韩雪倩的个性签名是“生活不止有眼前的苟且，还有诗和远方”…

…小学数学用“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…

““余数用r表示，r是remainder的首字母…”现代学者说。

…remainder（英语）：n.其他人员；剩余物；剩余时间；差数；余数；廉价出售的图书；滞销图书…

请看下集《欧几里得96、辗转相除法的计算原理；取模运算和取余运算》”

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

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