贡献者： int256
定义 1 最大公约数
两个不全为零的整数 $a$、$b$ 的最大公约数（greatest common divisor） $d$ 定义为能同时整除 $a$ 与 $b$ 的最大正整数。记作 $d = (a, b)$。类似的可以定义一组数 $\{a_i\}$ 的最大公约数 $(a_1, a_2, \dots, a_k) = (a_1, (a_2, (a_3, \dots)))$。
显然，若 $a$ 可表示为 $a = 2^{\alpha_1} \times 3^{\alpha_2} \times \cdots \times p_i^{\alpha_i}$，而 $b$ 可表示为 $b = 2^{\beta_1} \times 3^{\beta_2} \times \cdots \times p_j^{\beta_j}$，不失一般性地令 $i \ge j$（否则交换即可），此时令 $\beta_k = 0$ 若 $k > j$，则
\begin{equation}
d = (a, b) = 2^{\min(\alpha_1, \beta_1)} \times 3^{\min(\alpha_2, \beta_2)} \times \cdots \times p_i^{\min(\alpha_i, \beta_i)} ~.
\end{equation}
其中 $p_i$ 是第 $i$ 个素数。
定义 2 互素
若两个整数的最大公约数为 $1$，就称他们互素（coprime）。
定义 3 最小公倍数
两个都全为零的整数 $a$、$b$ 的最小公倍数 $l$ 定义为最小的同时是 $a$ 的倍数与 $b$ 的倍数的数。记作 $l = [a, b]$。类似的可以定义一组数 $\{b_i\}$ 的最小公倍数 $[b_1, b_2, \dots, b_l] = [b_1, [b_2, [b_3, \dots]]]$。
类似的，若 $a$ 可表示为 $a = 2^{\alpha_1} \times 3^{\alpha_2} \times \cdots \times p_i^{\alpha_i}$，而 $b$ 可表示为 $b = 2^{\beta_1} \times 3^{\beta_2} \times \cdots \times p_j^{\beta_j}$，不失一般性地令 $i \ge j$（否则交换即可），此时令 $\beta_k = 0$ 若 $k > j$，则
\begin{equation}
l = [a, b] = 2^{\max(\alpha_1, \beta_1)} \times 3^{\max(\alpha_2, \beta_2)} \times \cdots \times p_i^{\max(\alpha_i, \beta_i)} ~.
\end{equation}
其中 $p_i$ 是第 $i$ 个素数。
定理 1 最大公约数与最小公倍数的乘积
显然，对于两正数 $a, b$，$(a, b) \times [a, b] = a \times b$。
证明：由于 $\min(a, b) + \max(a, b) =a + b$。考虑若 $a$ 可表示为 $a = 2^{\alpha_1} \times 3^{\alpha_2} \times \cdots \times p_i^{\alpha_i}$，而 $b$ 可表示为 $b = 2^{\beta_1} \times 3^{\beta_2} \times \cdots \times p_j^{\beta_j}$，仍不失一般性地令 $i \ge j$（否则交换即可），此时令 $\beta_k = 0$ 若 $k > j$，则
\begin{equation}
(a, b) \times [a, b] = 2^{\min(\alpha_1, \beta_1) + \max(\alpha_1, \beta_2)} \times 3^{\min(\alpha_2, \beta_2) + \max(\alpha_2, \beta_2)} \times \cdots \times p_i^{\min(\alpha_i, \beta_i) + \max(\alpha_i, \beta_i)} ~.
\end{equation}
即
\begin{equation}
(a,b) \times [a, b] = 2^{\alpha_1 + \beta_1} \times 3^{\alpha_2 + \beta_2} \times \cdots \times p_i^{\alpha_i + \beta_i} = a \times b ~.
\end{equation}
证毕！
定理 2 辗转相除
\begin{equation}
\gcd(a, b) = \gcd(b , a \operatorname {mod} b) ~.
\end{equation}
证明：若 $a = kb + r$，其中 $r$ 为整数且 $0 \le r < b$，即 $r = a \operatorname {mod} b$。
设 $d$ 是 $a, b$ 的某公约数，则 $d|a$ 且 $d|b$。而 $r = a - cb$，两边同时除以 $d$ 将得到 $r/d = a/d - kb/d$，而等式右侧将是整数，故左侧也是整数，这指出 $d | r$，故 $d$ 也是 $b, r$ 的公约数。且若 $d$ 是 $b, r$ 的公约数，则 $d$ 必将是 $b, a=r+kb$ 的公约数。
综上，$a, b$ 的公约数的集合与 $b, r=a \operatorname {mod} b$ 的公约数的集合相同。故 $\gcd(b, a \operatorname {mod}b) = \gcd(a, b)$，证毕！
致读者： 小时百科一直以来坚持所有内容免费无广告，这导致我们处于严重的亏损状态。 长此以往很可能会最终导致我们不得不选择大量广告以及内容付费等。 因此，我们请求广大读者
热心打赏 ，使网站得以健康发展。 如果看到这条信息的每位读者能慷慨打赏 20 元，我们一周就能脱离亏损， 并在接下来的一年里向所有读者继续免费提供优质内容。 但遗憾的是只有不到 1% 的读者愿意捐款， 他们的付出帮助了 99% 的读者免费获取知识， 我们在此表示感谢。