欧几里得算法，辗转相除法的证明
由组合数到费马小定理到欧几里得引理到裴蜀定理到扩展欧几里得算法到欧几里得算法。
数论真好玩，我给你大拇哥🤣
大致流程：（对知识点预处理，更好理解，也为以后提供有用的产出，不白费时间）
设d是a，b的公约数，证明d也是b，a % b的公约数
设d是b，a % b的公约数，证明d也是a，b的公约数。
推出二者公约数集合相同，所以最大公约数也相同。
证明递归直到a % b== 0得到最大公约数。
必要知识：
1）涉及到一个运算封闭性。
加减乘都是封闭的，对结果取模可以转化为处处取模。
所以如果d | a,d | b ,则d | a * b,d | a + b,d | a - b
2）跳步逻辑：
设d是a，b的公约数
在设d这个未知数为a，b的公约数时，就说明d是a,b的任意公约数
3）a % b可以写成a - k * b;
4）公因数就是公约数
5）d | a是a % d == 0的意思，读作d 整除 a，反过来就是a被d整除
具体证明：
第一步：证明若d 是 a,b的公约数，则d也是b,a % b的公约数
设d是a，b的公约数
则有：
- d | a,d | b
由1得
- d | k * b
由1，2得：
- d | a - k * b,即 d | a % b;
由1，3得
d | b,d | a % b
得d为b,a % b的公约数，证毕。
第二步：证明若d是b，a % b 的公约数，则d也是a,b的公约数
设d是b，a % b 的公约数
则有：
- d | b,d | a % b
由1得
- d | k * b,d | a - k * b,
由2得
- d | a - k * b + k * b,即d | a
由1，3
d | b,d | a
所以d是a,b的公约数，证毕
第三步证明a,b的最大公约数 = b，a % b的最大公约数
由前两步：
a，b和b，a % b的公约数集合相同，所以a,b的最大公约数等于b,a % b的最大公约数。
第四步：证明a % b == 0时，此时的b为最大公约数
由此传入参数a,b递归求解，当传入函数的参数a % b == 0时得到最大公因数为设b1为此时的b
因为0 mod b1 == 0
所以b1 | 0,
而b1 | b1,
所以
b1 是b1和0的公因数，且易知是最大公因数。
所以gcd(b1,0) = b1
且gcd(a,b) 和 gcd(b1,0)的最大公约数相同，gcd(b1,0) = b1
所以，a,b的最大公约数就是b1
补充：
递归调用时的a,b大小问题：
int gcd(int a,int b){
if(b == 0) return a;
return gcd(b,a%b);
}
如果a < b
return gcd(b,a%b),
a % b = a,所以转化成了a > b的情况。
运用：最小公倍数。
1）算数基本定理指出任何大于1的数都可以唯一表示为质数乘积
证明：
假设已经证明了2~k可以用质数乘积表示
则证明k+1可以用质数乘积表示。
如果k+1是质数，则直接用本身表示。
若k+1是合数，由合数定义：
除了1和自身还能被其他数整除，
所以可以用之前已经表示过的数来表示
2）最大公因数是两个数质数集合的共有质数乘积
3）最小公倍数是两个数的质数集合的所有质数乘积
4）两数相乘，质数集合中共有的质数是二次方，如果除去这些相同的质数就得到了两个数的质数集合的所有质数，也就是最小公倍数