第五章：整除性与最大公因数（1）

假设 m 与 n 是整数，$m\neq 0$。m 整除 n 是指 n 是 m 的倍数，即存在整数 k 使得$n= mk$。如果 m 整除 n，我们记为$m|n$；如果$m$ 不整除$n$，我们记为$m\nmid n$。例如，由于$6=3·2$，所以$3|6$。$6$ 的因数是$1,2,3$。由于没有$5$ 的倍数等于$7$，所以$5\nmid7$。整除$n$ 的数称为$n$ 的因数。
如果已知两个整数，我们可以求其公因数，即整除它们两个的数。例如，由于$4|12$ 且$4|20$，所以$4$ 是$12$ 与$20$ 的公因数。注意，$4$ 是$12$ 与$20$ 的最大公因数。类似地，$3$ 是$18$ 与$30$ 的公因数，但不是最大的，因为$6$ 也是公因数。
两个数$a$ 与$b$（不全为零）的最大公因数是整除它们两个的最大数，记为$gcd(a,b)$。如果$gcd(a,b)=1$，我们称$a$ 与$b$ 互素。

本作品采用《CC 协议》，转载必须注明作者和本文链接