最大公因数与最小公倍数

$a,b$ 不全为零，它们的所有公因数里最大的那个，叫最大公因数，记作 $gcd(a,b)$，也写作 $(a,b)$。

所有公倍数里最小的正数，叫最小公倍数，记作 $lcm(a,b)$，也写作 $[a,b]$。

$gcd(a,b)=1$ 时，说 $a,b$ 互素。注意互素不要求两个数都是素数，$8$ 和 $9$ 就互素。

求 $gcd(1071,462)$，不用分解质因数：

$$1071=462\times 2+147$$ $$462=147\times 3+21$$ $$147=21\times 7+0$$

最后一个非零余数是 $21$，所以 $gcd(1071,462)=21$。

这个等式让两个大数越除越小，几步就到底。手算两位数、三位数的 gcd，辗转相除比分解质因数快得多。

证明思路：把 $a,b$ 分解成素数幂，$gcd$ 取每个素因子的最小指数，$lcm$ 取最大指数，两者相加正好等于 $a,b$ 中该素因子指数之和。

所以知道 gcd 和其中一个数，就能反求 lcm，反之亦然。

例1 辗转相除

求 $gcd(2026,1518)$。

解： $$2026=1518\times 1+508$$ $$1518=508\times 2+502$$ $$508=502\times 1+6$$ $$502=6\times 83+4$$ $$6=4\times 1+2$$ $$4=2\times 2+0$$

最后一个非零余数是 $2$，所以 $gcd=2$。

例2 用乘积关系

已知 $gcd(a,b)=6$，$lcm(a,b)=180$，求 $ab$。

解：$ab=gcd·lcm=6\times 180=1080$。

例3 互素的性质

证明：若 $gcd(a,b)=1$，且 $a\mid bc$，则 $a\mid c$。

解：由贝祖定理，存在整数 $x,y$ 使 $ax+by=1$。两边乘 $c$： $$acx+bcy=c$$ $a$ 整除 $acx$（这一步直接由 $a\mid acx$ 得出），也整除 $bcy$（因为 $a\mid bc$），所以 $a$ 整除它们的和 $c$。

这条性质叫“互素可约”，它补上了“除法不能随便约”的那个缺口：能约的前提是互素。

例4 求所有解

求所有的正整数 $a,b$，使 $a+b=30$ 且 $gcd(a,b)=5$。

解：设 $a=5m$，$b=5n$，$gcd(m,n)=1$。则 $5(m+n)=30$，$m+n=6$。

互素且和为 $6$ 的组合：$(1,5)$、$(5,1)$。（$2,4$ 不互素，$3,3$ 不互素）

所以 $(a,b)=(5,25)$ 或 $(25,5)$。

例5 三个数

求 $gcd(84,126,210)$ 与 $lcm(84,126,210)$。

解：分解：$84=2^2·3·7$，$126=2·3^2·7$，$210=2·3·5·7$。

$gcd$ 取最小指数：$2^1·3^1·7^1=42$。

$lcm$ 取最大指数：$2^2·3^2·5·7=1260$。

三个数不能再用 $gcd·lcm=$ 乘积，那条只对两个数成立。