记 \(a\) 和 \(b\) 最大公约数为 \(\gcd(a, b)\), 记 \(a\) 和 \(b\) 最小公倍数数为 \(lcm(a, b)\)。
设 \(a > b\)。
\(gcd(a, b) = gcd(b, a \mod b)\)。
证明如果 \(a\) 是 \(b\) 的倍数， 那么 \(\gcd(a,b) = b\)，如果 \(b = 0\)， 那么 \(\gcd(a, b) = a\)。
下面讨论 \(a\) 不是 \(b\) 的倍数的情况。
设 \(a = bk + r\)，那么 \(a \mod b = r\)，就是要证明 \(\gcd(a, b) = \gcd(b, r)\)。
记 \(\gcd(a, b) = x\)， 于是就有 \(a | x\)， \(b | x\)。
把上面的式子变一下，就是 \(r = a - bk\)，同时除以一个 \(x\)，于是 \(\frac{r}{x} = \frac{a}{x} - \frac{bk}{x}\)。
\(\because a | x\), \(b | x\)
\(\therefore a | x, bk | x\)
\(\therefore \frac{a}{x},\frac{bk}{x} \in \mathbb{Z}\)
\(\therefore \frac{a}{x} - \frac{bk}{x} \in \mathbb{Z}\)
及 \(\frac{r}{x} \in \mathbb{Z}\)
\(\therefore r | x\)。
那么 \(a, b\) 的约数就是 \(b, r\) 的约数，就可以得到 \(\gcd(a, b) = \gcd(b, r) = \gcd(b, a \mod b)\)。
得证。
求最小公倍数\(lcm(a, b) = a \div gcd(a, b) \times b\)。
证明由唯一分解可以得到
\(a = p_1^{a_1} \times p_2^{a_2} \times \dots \times p_n^{a_n}\)
\(b = p_1^{b_1} \times p_2^{b_2} \times \dots \times p_n^{b_n}\)。
那么最大公约数就是
\(\gcd(a, b) = p_1^{\min(a_1, b_1)} \times p_2^{\min(a_2, b_2)} \times \dots \times p_n^{\min(a_n, b_n)}\)
最小公倍数就是
\(lcm(a, b) = p_1^{\max(a_1, b_1)} \times p_2^{\max(a_2, b_2)} \times \dots \times p_n^{\max(a_n, b_n)}\)
显然 \(\gcd(a, b) \times lcm(a, b) = a \times b\)。
因此就有 \(lcm(a, b) = a \times b \div \gcd(a, b)\)。
然后还可以整一下，设 \(x = \gcd(a, b)\)
于是 \(a = x \times a'，b = x \times b'\)，于是就有 \(gcd(a', b') = 1\)
那么 \(lcm(a, b) = a' \times x \times b' \times x \div x = a' \times x \times b\)，可以发现这显然是最优的。
扩展欧几里得算法这个算法可以求解形如这样的二元一次方程 \(ax + by = gcd(a, b)\)， 其中 \(a，b\in \mathbb{Z}\)
求解不难发现有无数组解，我们这样设：
\(ax_1 + by_1 = gcd(a, b) \\ bx_2 + (a\mod b)y_2 = gcd(a, b \mod a) \)
由前面的欧几里得算法可以得到 \(gcd(a, b) = gcd(a, b \mod a)\)， 于是就有 \(ax_1 + by_1 = bx_2 + (a\mod b)y_2\)。
然后又有 \(a\mod b = a - (\lfloor \frac{a}{b} \rfloor \times b)\)。
于是就有 \(ax_1 + by_1 = bx_2 + (a - (\lfloor \frac{a}{b} \rfloor \times b))y_2\)
于是 \(ax_1 + by_1 = ay_2 + b(x_2 - (\lfloor \frac{a}{b} \rfloor) \times y_2)\)
因为 \(a = a, b = b\)， 所以 \(x_1 = y_2, y_1 = x_2 - (\lfloor \frac{a}{b} \rfloor) \times y_2\)。
可以发现上面设的分别是欧几里得算法前后两种状态，所以在求欧几里得的时候就可以顺便把这组解求了。