用欧几里德辗转相除法,求两个数的最大公约数和最小公倍数；我完全看不懂 非常感激,在此先谢过了啊
问题描述：
用欧几里德辗转相除法,求两个数的最大公约数和最小公倍数；
我完全看不懂
非常感激,在此先谢过了啊
答
不妨假设：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 ...