如何证明两个数的最大公因数和最小公倍数的乘积等于这两个数的乘积

这个可以算是初等数论里面的知识的。

我是在给家里的小同志讲小学奥数的时候遇到的。老师告诉他会用就行，我作为一个长辈，有必要给他讲一讲其中的原理。

这个问题给我来证明，得分为两点。

主体

求证：两个自然数的最大公因数和最小公倍数的乘积等于这两个数的乘积。

证明：

不妨设两个自然数分别为 $M、N$，

易证，任意一个自然数 $N$ 可以被分解成多个质数因子的乘积，且这样的分解唯一，所以，

$$
M = p_1^{i_1} p_2^{i_2} \dots p_k^{i_k} \dots p_m^{0} \dots
$$

$$
N = p_1^{j_1} p_2^{j_2} \dots p_k^{j_k} \dots p_n^{0} \dots
$$

我们把 $M$ 和 $N$ 分别记作，

$$
M = (i_1, i_2, i_3, \dots, i_m, 0, \dots)
$$

$$
N = (j_1, j_2, j_3, \dots, j_n, 0, \dots)
$$

则，最大公因数和最小公倍数分别为，

$$
gcd(M, N) = (min{i_1, j_1}, min{i_2, j_2}, min{i_3, j_3}, \dots)
$$

$$
lcm(M, N) = (max{i_1, j_1}, max{i_2, j_2}, max{i_3, j_3}, \dots)
$$

而，

$$
min{i, j} + max{i, j} = i + j
$$

因此，得证。

附加

关于 gcd 和 lcm 我没有证过上面的形式，所以这里证明一下。

不妨设，

$$
M = p_1^{i_1} p_2^{i_2} \dots p_k^{i_k}
$$

$$
N = p_1^{j_1} p_2^{j_2} \dots p_k^{j_k}
$$

求证：

$$
g = gcd(M, N) = (min{i_1, j_1}, min{i_2, j_2}, min{i_3, j_3}, \dots, min{i_k, j_k})
$$

注：这里借用了上面的形式。

证明：

先证必要性：显然，$g \mid a$ 且 $g \mid b$。

再证充分性：

不妨假设设 $m = g \times p_n$，其中，$p_n$ 是上面任意一个质数，

再不妨设 $i_n < j_n$，

因此，$min(i_n, j_n) = i_n$，

所以 $m$ 中由 $i_n + 1$ 个质因子，

故 $m \nmid a$ 不为 $M, N$ 公因数。

原命题得证。

---

参考：

1、https://www.zhihu.com/question/326472814
2、https://www.cnblogs.com/JustinRochester/p/12355660.html