Question

欧几里德辗转相除法

用欧几里德辗转相除法，求两个数的最大公约数和最小公倍数；
我完全看不懂
请哪位数学达人帮我解释下啊
非常感激，在此先谢过了啊

Answer 1

不妨假设：a、b（a>=b>0）的最大公约数为c。
引理：令t为 a 除以 b 的余数（t不为零），则b与t的的最大公约数也为c。
引理的证明比较简单，简单讲一下。
证明：由题设a、b可以写成：a=k1*c，b=k2*c；其中k1、k2为正整数。
t为a 除以b 的余数（t不为零），于是a=kb+t，其中k为正整数。
t = a - kb = k1*c - k*k2*c，所以t也是c的倍数。
引理得证。

由引理，我们就有了辗转相除法。
在求a、b（a>=b>0）的最大公约数时，我们可以先求得a÷b的余数t，再求t与b的最大公约数，结果是一样的。在求b与t（显然b>t）的最大公约数时，我们还可以用同样的方法继续通过求余来求。
直到当a÷b的余数为0时，显然它们的最大公约数为b。这时计算就完了。
这就是辗转相除法。