辗转相除法（欧几里得算法）+最小公倍数证明

辗转相除法

定义：求两个数的最大公约数

步骤：

①两数a、b（b<a），r=a%b，即 a = kb+r (0=< r<b);

②若r = 0，则b是a和b的最大公约数。

③若r不为0，重复以上步骤（注：此时a = b,b = r, “=” 为赋值操作）。

证：gcd(a,b) = gcd(b,a%b)

令 a = kb+r, 设gcd为a 和 b的最大公约数，

则gcd也是b 和 r 的最大公约数，证明如下：

令 a=x*gcd，b=y*gcd，则 r = a-kb = (x-ky)*gcd；

所以可以进行重复的有限次数的取余操作，直到 r=0,即可求出最大公约数gcd。

最小公倍数

证明：两数最小公倍数为两数之积/最大公约数，

即最小公倍数 lcm = a*b/gcd.

因为 a = x*gcd , b = y*gcd ,其中 x,y互质，

令 lcm = a*z1 = b*z2，得x*z1 = y*z2，

可知 z1 = y，所以 lcm = x*y*gcd,

得 lcm = a*b/gcd。

代码网上已有多份，不再进行实现，仅作证明。

注：因作者知识水平有限，若有不足之处，欢迎补充。