4.1. 整除性和模算术

本章将要展开的内容是基于整除性的概念，一个整数被一个正整数，得到一个商和一个余数。与这些余数打交道导致模算术，它在数学中起着重要的作用并广泛应用于计算机科学领域中。

除法

定义1

如果 $a$ 和 $b$ 是整数且 $a \ne 0$，我们称 $a$ 整除 $b$ 如果有整数 $c$ 使得 $b = ac$ ，或者等价地，如果$\displaystyle \frac{b}{a}$是一个整数。当 $a$ 整除 $b$ 时，我们称$a$是$b$的一个因子或除数，而 $b$ 是 $a$ 的一个倍数。用记号 $a|b$ 表示 $a$ 整除 $b$。当 $a$ 不能整除 $b$ 时则写成 $a \nmid b$。

**评注 ** 可以用两次把 $a | b$ 表示成 $\exist\: c(ac = b)$，其中论域是整数集合。

定理1

令 $a, b, c$ 为整数，其中 $a \ne 0$。则
(i) 如果 $a | b$ 和 $a | c$，则 $a | (b + c)$
(ii) 如果 $a | b$，那么对所有整数 $c$ 都有 $a | bc$
(iii) 如果 $a | b, b | c$，则 $a | c$

证(i)
如果 $a | b$ 和 $a | c$，则存在整数$s$ 和 $t$ 满足 $b = as, c = at$。因此

$$b + c = as + at = a(s + t)$$

于是，$a$ 整除 $b + c$

推论1

如果$a, b, c$ 是整数，其中 $a \ne 0$，使得$a | b$和 $a | c$，那么当$m$和$n$是整数时有$a | mb + nc$

$$\begin{array}{lll} a | b & a | mb & (ii)\\ a |c & a |nc & (ii) \\ & a | mb + nc & (i) \end{array}$$

除法算法

定理2

除法算法（division algorithm）。令$a$为整数，$d$为正整数。则存在唯一整数$q$和$r$，满足$0 \le r < d$，使得$a = dq + r$。

---

定义2

在除法算法的等式中，d称为是除数，a称为是被除数，q称为是商，r称为是余数。下面的记号来表示商和余数

$$q = a\: \textbf{div}\: d, r = a \:\textbf{mod}\: d$$

这里的$d$是模

模算术

定义3

如果$a$和$b$为整数而$m$为正整数，则当$m$整除$a-b$时称$a$模$m$同余$b$。用记号$a \equiv b (\bmod\: m)$表示$a$模$m$同余$b$。我们称$a \equiv b (\bmod\: m)$为同余式（congruence），而那个m是它的模（modulus）。如果$a$和$b$不是模m同余的，则写成$a \neq b (\bmod\: m)$