第五章：整除性与最大公因数（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 协议》，转载必须注明作者和本文链接