最大公约数、最小公倍数与欧几里得算法

从 $a$ 中减去 $b$ 的倍数不会凭空产生或消除与 $b$ 的公因数:任何同时整除 $a$ 和 $b$ 的数也必然整除余下的 $r=a-bq$,反之亦然。

第一步(公因数集合相同)。设整数 $d$ 同时整除 $a$ 和 $b$,即对整数 $x,y$ 有 $a=dx$、$b=dy$。则 $r=a-bq=dx-dyq=d(x-yq)$,故 $d\mid r$,即 $d$ 同时整除 $b$ 和 $r$。反之,若 $d$ 同时整除 $b$ 和 $r$,设 $b=dy$、$r=dz$,则 $a=bq+r=dyq+dz=d(yq+z)$,故 $d\mid a$,即 $d$ 同时整除 $a$ 和 $b$。

第二步(最大公约数相等)。由于数对 $(a,b)$ 与 $(b,r)$ 拥有完全相同的公因数集合,它们的最大元素必然相同:$\gcd(a,b)=\gcd(b,r)$。

第三步(有限步终止)。每一步带余除法产生的余数都满足 $0\le r<b$,因此第二个数构成的序列 $b > r_1 > r_2 > \cdots \ge 0$ 是严格递减的非负整数序列。这样的序列最多经过 $b$ 步就会到达 $0$;在 $\gcd(r_{k-1},r_k)=\gcd(r_k,0)=r_k$ 这一步,最后一个非零余数 $r_k$ 就是 $\gcd(a,b)$。

对每个质数 $p$,$\gcd(a,b)$ 取 $p$ 在 $a,b$ 中较小的指数,而 $\operatorname{lcm}(a,b)$ 取较大的指数;两个数中较小者与较大者相加,总等于这两个数之和。

第一步。对所有质数 $p$ 写出 $a$ 和 $b$ 的质因数分解:$a=\prod_p p^{e_p}$,$b=\prod_p p^{f_p}$,其中 $e_p,f_p\ge0$ 且只有有限个指数非零。

第二步。正整数 $d=\prod_p p^{c_p}$ 同时整除 $a$ 和 $b$,当且仅当对每个 $p$ 有 $c_p\le e_p$ 且 $c_p\le f_p$,故最大公因数取 $c_p=\min(e_p,f_p)$:$\gcd(a,b)=\prod_p p^{\min(e_p,f_p)}$。对公倍数做对偶推理,取同时不小于两者的最小指数,得 $\operatorname{lcm}(a,b)=\prod_p p^{\max(e_p,f_p)}$。

第三步。对任意两个实数都有 $\min(e_p,f_p)+\max(e_p,f_p)=e_p+f_p$。因此将两个乘积按质数逐项相乘,即得 $\gcd(a,b)\cdot\operatorname{lcm}(a,b)=\prod_p p^{\min(e_p,f_p)+\max(e_p,f_p)}=\prod_p p^{e_p+f_p}=\left(\prod_p p^{e_p}\right)\left(\prod_p p^{f_p}\right)=ab$。