定义：如果 \(a\) 是 \(b\) 的约数，即 \(a \bmod b=0\)，记为 \(a \mid b\)。
- 如果 \(a \mid b\) 并且 \(a \mid c\)，那么 \(a \mid (bx+cy)\)
1. 最大公约数
记 \(\gcd(a,b)\) 为 \((a,b)\)。
显然 \(d \mid (a,b)\) 等价于，\(d \mid a\) 且 \(d \mid b\)
显然 \((a,b)=(a+b,b)=(a-b,b)=(a \bmod b,b)\)
1.1 更相减损术
由于 \((a,b)=(b,a)=(a-b,b)\)，所以每次让大数减小数，直到 \(a=b\) 返回 \(a\) 即可。
由于减法高精度比较容易实现，所以一般用于高精度。
1.2 辗转相除法
又名欧几里得算法
因为 \((a,b)=(b,a)=(a \bmod b,b)\)，所以每次让大数模小数，如果 \(b=0\)，那么返回 \((0,a)=a\)。
辗转相除法的时间复杂度为 \(\mathcal{O}(\log n)\)，而更相减损术复杂度复杂度有可能劣化为 \(\mathcal{O}(n)\)，所以一般都是用辗转相除法求 \(\gcd\)。
2. 最小公倍数
记 \(\operatorname{lcm}(a,b)\) 为 \([a,b]\)。
最小公倍数与最大公约数的关系是 \([a,b] \times (a,b)=a \times b\)