1.原理

辗转相除法由古老的更相减损术演变而来，其原理如下：

首先介绍下更相减损术的原理，假设有两个数161和63，我们要求这两个数的最大公因数，不妨假定这个最大公因数为m，我们可以将较大的数161看成63+98，63与98的和161可以被m整除，其中63也可以被m整除，自然98可以被m整除；所以这个问题就转换为求98和63的最大公因数m（和上面m相等） 将98看成63+35，其中63可以被m整除，和98也能被m整除，故35也可以被m整除；所以问题进一步转换为求35和63的最大公因数m（和上面m相等） 同理转换为求 (63-35)=>28和35 的最大公因数 然后转换为求28和7的最大公因数 …（一直减呀减） 后来转换为求7和7的最大公因数 最后转换为求7和0的最大公因数 输出第一个数字即可；这就是相减损术的原理

引用链接：https://blog.csdn.net/weixin_43886797/article/details/85569998

 辗转相除在更相减损的基础上，把依次相减直接使用取余数来替代，效率更高。

2.最大公约数（Greatest Common Divisor，GCD）

公约数，也叫公因数，是两个数之间的公共的约数（因数）。

明白了辗转相除的原理之后实现起来十分简单，可以直接用循环或递归实现。

需要注意的是，x和y 的大小关系不影响GCD的实现，因为在进行第一次取余操作时，如果x<y，则有x%y=x，这时候进行后续的换位操作，两数会交换位置，最终仍是大数在前，小数在后。

（1）循环实现

int GCD(int x, int y) //循环实现GCD { int z; while (y) { z = x % y; x = y; y = z; } return x; }

（2）递归实现 

int GCD(int x, int y)//递归实现GCD { if (y == 0) return x; else return GCD2(y, x % y); }

3.最小公倍数（Least Common Multiple，LCM）

最小公倍数=数字1*数字2/最大公约数，即最小公倍数为两数相乘后除以最大公约数。直接利用上述的GCD可求。

int LCM(int x, int y) { return x * y / GCD(x, y); }