最大公约数与最小公倍数

贡献者： int256

　　 显然，若 $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$，则

　　 类似的，若 $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$，则

　　 证明：由于 $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$，则

　　 证明：若 $a=kb+r$，其中 $r$ 为整数且 $0\le r<b$，即 $r=a\mathrm{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\mathrm{mod}b$ 的公约数的集合相同。故 $gcd(b,a\mathrm{mod}b)=gcd(a,b)$，证毕！