可除性

可除性是数论真正的起点，因为它将整数转化为一个具有结构的系统：你不再将数字仅仅视为“数量”，而是将其看作彼此之间可以或不可以相互契合的组成部分。借助单一的结构 a\mid b，你可以表达从化简与因式分解的判定准则，到诸如欧几里得算法等核心过程的本质，而该算法使得即使面对大整数，也能够在极短时间内计算最大公约数。此外，可除性还是在应用数学与计算机科学中反复出现的思想的技术基础：同余、模算术、验证机制、编码，以及（在后续内容中）密码学。从本质上说，掌握可除性，就是学会在整数中识别那些不可见的模式，并将其转化为始终有效的操作过程。

学习目标
完成本讲义后，学生将能够：

1. 理解整数之间的可除关系。
2. 理解可除性的定义及其性质。
3. 发展与可除性相关的数学结论和定理的证明能力。

内容索引
可除性的定义
可除性的基本性质
习题

可除性的定义

“a 整除 b”这一非正式想法，在将其表述为整数之间的关系时才变得精确。我们称一个整数 a 整除 一个整数 b，如果 b 可以表示为 a 的一个精确倍数。该定义是本讲义其余内容的基础，因为它将诸如“恰好整除”之类的表述转化为一个可验证的判定标准。

定义。 设 a,b\in\mathbb{Z} 且 a\neq 0。我们称 a 整除 b，并记为 a\mid b，当且仅当存在一个整数 k\in\mathbb{Z} 使得 b=ka。否则，记为 a\nmid b。

a\mid b := (\exists k \in \mathbb{Z})(b = ka )

在该定义中，数 k 被称为与该可除性相关的 商（或因子）。例如，断言 6\mid 42 等价于断言存在 k\in\mathbb{Z} 使得 42=6k；在此情形下，只需取 k=7。

需要注意的重要事项

• 条件 a\neq 0 是至关重要的。因为如果试图允许 a=0，则可除性的条件将要求存在 k\in\mathbb{Z} 使得 b=0\cdot k。然而，对所有 k 都有 0\cdot k=0，因此唯一的可能性是 b=0。在这种情况下，并不存在一个由该关系“确定”的 k，因为任意 k\in\mathbb{Z} 都满足 0=0\cdot k。换言之，非正式的表达 k=b/a 将变为 k=0/0，而这是没有定义的。为了避免这种退化情形（在其中“商”的概念不再具有意义），必须要求 a\neq 0。因此，关系 0\mid b 不被视为有效。
• 相反地，对于所有满足 a\neq 0 的 a\in\mathbb{Z}，命题 a\mid 0 都成立，因为只需取 k=0，便有 0=a\cdot 0。

由该定义可以推出一个我们将反复使用的等价表述：断言 a\mid b 等价于断言 b 属于 a 的整数倍集合，即 b\in a\mathbb{Z}，其中 a\mathbb{Z}=\{ak:\,k\in\mathbb{Z}\}。这种写法强调了可除性并非一种“技巧”，而是一种用于描述 \mathbb{Z} 中高度结构化子集的方式。

可除性的基本性质

• 自反性： a\mid a。
  证明：

  \begin{array}{rll} (1)&\vdash a=ka \leftrightarrow k=1 &\text{; $\mathbb{Z}$ 中的乘法单位元}\\ (2)&\vdash(\exists k \in \mathbb{Z})(a=ka) &\text{; 存在量词引入 (1)}\\ (3) &\vdash a \mid a &\text{; 可除性的定义 (2)} \\ &\blacksquare & \end{array}

• 传递性： 若 a\mid b 且 b\mid c，则 a\mid c。

  证明：

  \begin{array}{rll} (1)& \{a\mid b , b\mid c\} \vdash (\exists k_1\in\mathbb{Z})(b=k_1a) &\text{; 可除性的定义，前提}\\ (2)& \{a\mid b , b\mid c\} \vdash (\exists k_2\in\mathbb{Z})(c=k_2b) &\text{; 可除性的定义，前提}\\ (3)& \{a\mid b , b\mid c\} \vdash (\exists k_1,k_2\in\mathbb{Z})(b=k_1a \wedge c=k_2b) &\text{; $\exists$-合并 (1,2)}\\ (4)& \{a\mid b , b\mid c\} \vdash (\exists k_1,k_2\in\mathbb{Z})(k_2b=k_1k_2a \wedge c=k_2b) &\text{; 由(3)}\\ (5)& \{a\mid b , b\mid c\} \vdash (\exists k_1,k_2\in\mathbb{Z})( c=k_1k_2a) &\text{; 由(4)}\\ &\text{量词内部的代数运算}& \\ (6)& \{a\mid b , b\mid c\} \vdash (\exists k\in\mathbb{Z})( c=ka) &\text{; 由(5)}\\ &\text{$\mathbb{Z}$ 对乘法的封闭性}& \\ (7)& \{a\mid b , b\mid c\} \vdash a\mid c &\text{; 可除性的定义 (6)}\\ (8)& \vdash (a\mid b \wedge b\mid c) \rightarrow a\mid c &\text{; $\wedge$-消去 (7)}\\ &\blacksquare& \end{array}

• 与加法和减法的相容性： 若 a\mid b 且 a\mid c，则 a\mid (b+c) 且 a\mid (b-c)。
  证明：

  \begin{array}{rll} (1)&\{a\mid b, a\mid c\}\vdash (\exists k_1 \in \mathbb{Z})(b=k_1 a) &\text{; 可除性的定义，前提}\\ (2)&\{a\mid b, a\mid c\}\vdash (\exists k_2 \in \mathbb{Z})(c=k_2 a) &\text{; 可除性的定义，前提}\\ (3)&\{a\mid b, a\mid c\}\vdash (\exists k_1, k_2 \in \mathbb{Z})(b=k_1 a \wedge c=k_2 a) &\text{; $\exists$-合并 (1,2)}\\ (4)&\{a\mid b, a\mid c\}\vdash (\exists k_1, k_2 \in \mathbb{Z})(b+c= (k_1+k_2)a) &\text{; 由(3)}\\ &\text{量词内部的代数运算。}& \\ (5)&\{a\mid b, a\mid c\}\vdash (\exists k \in \mathbb{Z})(b+c= ka) &\text{; 由(4)}\\ &\text{$\mathbb{Z}$ 对加法的封闭性。}& \\ (6)&\{a\mid b, a\mid c\}\vdash a\mid (b+c) &\text{; 可除性的定义 (5)}\\ (7)&\vdash (a\mid b \wedge a\mid c) \rightarrow a\mid (b+c) &\text{; $\wedge$-消去 (6)}\\ (8)&\{a\mid b, a\mid c\}\vdash (\exists k_1, k_2 \in \mathbb{Z})(b-c= (k_1-k_2)a) &\text{; 由(3)}\\ &\text{量词内部的代数运算。}& \\ (9)&\{a\mid b, a\mid c\}\vdash (\exists \overline{k} \in \mathbb{Z})(b-c= \overline{k}a) &\text{; 由(8)}\\ &\text{$\mathbb{Z}$ 对减法的封闭性。}& \\ (10)&\{a\mid b, a\mid c\}\vdash a\mid (b-c) &\text{; 可除性的定义 (9)}\\ (11)&\vdash (a\mid b \wedge a\mid c) \rightarrow a\mid (b-c) &\text{; $\wedge$-消去 (10)}\\ (12)&\vdash (a\mid b \wedge a\mid c) \rightarrow \left(a\mid (b+c) \wedge a\mid (b-c)\right) &\text{; 在结论中进行 $\wedge$-引入 (7,11) }\\ &\blacksquare& \end{array}

• 与乘积的相容性： 若 a\mid b，则对任意 c\in\mathbb{Z} 都有 a\mid (bc)。
  证明：

  \begin{array}{rll} (1)& \{a\mid b\}\vdash (\exists k\in\mathbb{Z})(b=ka) &\text{; 可除性的定义，前提}\\ (2)& \{a\mid b\}\vdash \left(\forall c \in \mathbb{Z}\right) (\exists k\in\mathbb{Z})(cb=cka) &\text{; 由(1)，$\forall$-引入（$c$ 任意）}\\ &\text{量词内部的 $\mathbb{Z}$ 中的代数运算。}&\\ (3)& \{a\mid b\}\vdash \left(\forall c \in \mathbb{Z}\right) (\exists \overline{k}\in\mathbb{Z})(cb=\overline{k}a) &\text{; 由(2)，封闭性：}\overline{k}=ck\\ (4)& \{a\mid b\}\vdash \left(\forall c \in \mathbb{Z}\right) (a \mid cb) &\text{; 可除性的定义 (3)}\\ (5)& \vdash a\mid b \rightarrow \left(\forall c \in \mathbb{Z}\right) (a \mid cb) &\text{; 推导定理 (4)}\\ &\blacksquare& \end{array}

定理：除数的界

若 b\neq 0 且 a\mid b，则 |a|\le |b|。

证明：

\begin{array}{rll} (1) &\{b\in \mathbb{Z}\setminus\{0\} , a\mid b\}\vdash b \neq 0 & \text{; 前提} \\ (2) &\{b\in \mathbb{Z}\setminus\{0\} , a\mid b\}\vdash (\exists k \in \mathbb{Z}) (b=ka) & \text{; 可除性的定义，前提} \\ (3) &\{b\in \mathbb{Z}\setminus\{0\} , a\mid b\}\vdash (\exists k \in \mathbb{Z}) (|b|=|k||a|) & \text{; 绝对值的性质，由(2)} \\ (4) &\{b\in \mathbb{Z}\setminus\{0\} , a\mid b\}\vdash (\exists k \in \mathbb{Z}) (k\neq 0 \wedge |b|=|k||a|) & \text{; 由(1,3)} \\ (5) &\{b\in \mathbb{Z}\setminus\{0\} , a\mid b\}\vdash (\exists k \in \mathbb{Z}) (1\le |k| \wedge |b|=|k||a|) & \text{; 由(4)，若 }k\neq 0\Rightarrow |k|\ge 1 \\ (6) &\{b\in \mathbb{Z}\setminus\{0\} , a\mid b\}\vdash |a|\le |b| & \text{; 由(5)} \\ &\blacksquare& \end{array}

习题

1. 证明当 b=0 时，“除数的界”定理不一定成立。
2. 考虑一个集合 A 及其上的一个关系 \rho。若元素 x,y\in A 满足 x 通过 \rho 与 y 相关，则记为 x\rho y。若关系 \rho 满足以下条件，则称其为 A 上的偏序关系：

   a)(\forall x\in A) (x\rho x)，
   b) (\forall x,y\in A) ( (x\rho y \wedge y\rho x) \rightarrow x=y)
   c) (\forall x,y,z\in A) ( (x\rho y \wedge y\rho z) \rightarrow x\rho z)。

   证明可除关系在整数集合上构成一个偏序关系。

3. 用数学归纳法证明：若 a\mid b_1, a\mid b_2, \cdots, a\mid b_n，则对任意集合 \{x_i\}_{i=1}^n \subset \mathbb{Z} 都有 a\mid \sum_{i=1}^n b_i x_i。此外，证明若 a\mid b_i，其中 i\in \{1,2,3,\cdots, n\}，且 c 可以表示为这些 b_i 的线性组合，则 a\mid c。
4. 若 a\neq 0，证明集合 \{x\;:\; d\mid a\} 是一个有限集。
5. 固定一个 n\in\mathbb{Z}^+，并令

   S=\{d\,:\,d\in\mathbb{Z}^+ \wedge d\mid n\}

   证明：

   1. d\in S \leftrightarrow n/d\in S
   2. 若将 S 的元素按递增顺序排列：1=d_1 \lt d_2 \lt \cdots \lt d_t =n，则相应的元素 n\mid d_i（其中 i \in \{1,2,\cdots, t\}）按递减顺序排列。
6. 设 a,b\in\mathbb{Z}^+ 且 ab=c。证明 \min\{a,b\}\le \sqrt{c}。
7. 若整数 n 满足 2\mid n，则称其为偶数；若 2\nmid n，则称其为奇数。证明以下和与差的性质：
   1. 两个偶数的和是偶数。
   2. 两个奇数的和是偶数。
   3. 一个偶数与一个奇数的差是奇数。
8. 若 n 是一个不等于 \pm 1 的奇数，证明 n 不可能同时整除两个连续的偶数。
9. 设 a,b,n\in\mathbb{Z} 且 |a-b|\lt |n|。证明 n 既不能整除 a，也不能整除 b。
10. 设 a\in\mathbb{Z}。证明：
    1. (\forall n \in \mathbb{Z})(a\mid n) \leftrightarrow a=\pm 1
    2. (\forall n \in \mathbb{Z})(n\mid a) \leftrightarrow a=0
11. 设 a,b,c\in\mathbb{Z} 且假设 c\neq 0。证明若 ac\mid bc，则必有 a\mid b。