证明最大公因数和最小公倍数的关系

问题

设$a$、$b$的最大公因数为$m$，最小公倍数为$n$（$a,b,m,n \in N^+$），求证$ab = mn$。

证明

先证明$\frac{ab}{m}$是$a$、$b$的公倍数。

设$a = pm$（$p \in N^+$），$b = qm$（$q \in N^+$）。

可知$p$、$q$互质。因为如果$p$、$q$不互质，即$p$、$q$存在大于$1$的公因数，则$m$就不是$a$、$b$的最大公因数了。

$\frac{ab}{m} = \frac{pm \cdot qm}{m} = pqm$。$p$、$q$、$m$都是正整数，则$\frac{ab}{m}$也是正整数。

因为$\frac{ab}{m} = pm \cdot q = a \cdot q$，所以$\frac{ab}{m}$是$a$的倍数。

因为$\frac{ab}{m} = qm \cdot p = b \cdot p$，所以$\frac{ab}{m}$是$b$的倍数。

所以，$\frac{ab}{m}$是$a$、$b$的公倍数。

再证明$\frac{ab}{m}$是$a$、$b$的所有公倍数中最小的。

反证法。假设存在$x$也是$a$、$b$的公倍数，且$x<\frac{ab}{m}$。

设$x = ar$（$r \in N^+$），则有$x = pmr$。

因为$x < \frac{ab}{m}$，即$pmr < pmq$，所以$r<q$。

设$x = bs$（$s \in N^+$），则有$x = qms$。

因为$\frac{x}{m} = pr = qs$，所以$\frac{x}{m}$是$p$、$q$、$r$、$s$的倍数。

对于$\frac{x}{m} = pr$，它是$q$的倍数，$p$、$q$互质，有以下2种情况：

1. $q > 1$，则$p$不可能是$q$的倍数，那么$r$一定是$q$的倍数，则有$r \ge q$，这与$r<q$矛盾；
2. $q = 1$，则$p$是$q$的倍数，同时$r$也是$q$的倍数，同样有$r \ge q$，与$r < q$矛盾。

同理，有$s<p$和$s \ge p$的矛盾。

所以不存在比$\frac{ab}{m}$更小的公倍数，即$\frac{ab}{m}$就是最小公倍数，即$n = \frac{ab}{m}$。

即得$ab = mn$。