整除

整除询问的是一个数能否由另一个数通过整数倍得到。$a\mid b$ 就是说 $b$ 落在倍数集合 $a\mathbb{Z}$ 中；一旦 $b$ 是 $a$ 的倍数，$b$ 的每个倍数也都是 $a$ 的倍数，所以 $b\mathbb{Z}\subseteq a\mathbb{Z}$。因此数的整除方向，与倍数集合的包含方向相反。

正负号不改变倍数集合：$a\mathbb{Z}=(-a)\mathbb{Z}$。只考虑正整数后，每个倍数集合有唯一的正生成元，整除关系就成为偏序。这一偏序按因子关系排列整数，例如 $2$ 与 $3$ 虽有大小之分，却互不整除。

$3\mid 12$，因为 $12=3\cdot 4$；$5\nmid 12$，因为没有整数 $c$ 满足 $12=5c$。乘积的情况则要看因子如何组合：$6\mid 2\cdot 3$，但 $6$ 既不整除 $2$，也不整除 $3$。若除数是素数，就有更强的性质：整除乘积时必整除至少一个因子。

在一般整环中，同样用 $b=ac$ 定义整除，只是 $a,b,c$ 都取自该环。例如在高斯整数 $\mathbb{Z}[i]$ 中，

所以 $1+i\mid 2$；又因 $1-i=-i(1+i)$，二者只相差单位 $-i$，彼此整除，是一对相伴元。在整环中，把相伴元归为一类后，整除在这些类上构成偏序。

在带零因子的环中，乘法消去可能失败。例如在 $\mathbb{Z}/8\mathbb{Z}$ 中

但 $[1]\ne [5]$，因为差值 $[4]$ 乘以 $[2]$ 就变为零。整环中没有这种现象：若 $c\ne 0$ 且 $ac=bc$，则 $(a-b)c=0$ 迫使 $a=b$。

对不全为零的整数 $a,b$，先取 $|a|,|b|$，再在非负整数的整除偏序中比较；其中 $0$ 是最大元。最大公因数公理库最大公约数Greatest common divisor · GCD同时整除两个整数且被所有公约数整除的非负整数。正是 $|a|,|b|$ 在这个偏序中的最大公共下界，Euclid 算法公理库整数欧几里得算法Euclidean algorithm for integers反复使用带余除法计算最大公约数的有限算法。可以求出它。素元公理库素元Prime element整除乘积时必整除至少一个因子的非零非单位元素。则用对乘积的整除性质定义，使因子能在不同分解之间配对。对正模数 $n$，同余 $a\equiv b(\mathrm{mod}n)$ 也可写成 $n\mid (a-b)$：两个数的差属于同一个倍数集合 $n\mathbb{Z}$。