贡献者： 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)$，证毕！