资讯详情

我声称这就是 2 号写的，但这几天情绪不稳定，今天发。

由欧几里得算法，我们可以递归下降地枚举证明 \(gcd(a, b) = gcd(b, a - b)\) 。

由唯一分解定理

\[gcd(a, b) = p_0^{min(a_0, b_0)} p_1^{min(a_1, b_1)} p_2^{min(a_2, b_2)} \cdots p_k^{min(a_k, b_k)} \]

有两个引理。

引理一：
\(gcd(a, b) = gcd(b, a)\) 。

引理二：
\(gcd(a, b, c) = gcd(gcd(a, b), c)\) 。

那么

\[gcd(a, b, c) = gcd(gcd(a, b - a), c) = gcd(gcd(a, c), b - a) = gcd(gcd(a, c - a), b - a) = gcd(a, b - a, c - a) \]

显然我们可以递归扩展到我们的常见结论

\[gcd(x_1, x_2, x_3, \cdots, x_n) = gcd(x_1, x_2 - x_1, x_3 - x_1, \cdots, x_n - x_1) \]

也可以自由递归构造出其他各自结构看起来很不优美的结论。