整除

1. 概述

于 初等数论 中, 整数的整除 描述一个 整数 是否为另一个整数的整数倍. 它是研究 因数、倍数、素数 与最大公因数的基础关系.

2. 定义

定义 1 (整数的整除)

设 . 称 整除 , 当存在 使：

记号 2 (整数的整除)

整除 记为 ; 若 不整除 , 则记为 .

别名 3 (整除)

若 , 则称 为 的 因数 或约数, 并称 为 的 倍数.

3. 例子

例子 4 (初步例子)

• , 因为 ;
• , 因为 ;
• , 因为不存在 使 ;
• 每个整数都 整除 , 但只有 能被 整除.

例子 5 (正负整数的带余除法)

• ;
• ;
• .

三式中的余数都满足 .

4. 相关性质

命题 6 (整除的基本性质)

设 , 则：

1. 且 ;
2. 当且仅当 ;
3. 若 且 , 则 ;
4. 若 且 , 则 ;
5. 若 , 则 ; 当 时, 反命题也成立;
6. 且 当且仅当 ;
7. 若 且 , 则 .

证明 7 (整除的基本性质)

1. 由 与 得证.
2. 若 , 则 对某个 成立; 反之 , 故 .
3. 写 与 , 则 .
4. 写 与 , 则 .
5. 若 , 则 , 故 . 反之, 若 且 , 则 ; 由整数乘法的消去律得 , 因而 .
6. 若 且 , 写 与 . 当 时也有 ; 当 时, 由 消去 得 , 故 , 从而 . 反之, 若 , 则 或 , 因而二者彼此 整除.
7. 写 . 因 , 有 , 所以 且 .
   

定理 8 (整数上的带余除法)

设 且 . 存在唯一的 使：

证明 9 (整数上的带余除法)

存在性

令 , 并考虑 集合：

取 即知 非空. 由 良序性原理, 存在最小元 . 若 , 则：

且 , 与 的最小性矛盾. 因而 . 若 , 取 ; 若 , 取 , 均有 .

唯一性

若另有 且 , 则：

因 , 而 , 只能有 . 于是 , 再由 得 .

别名 10 (带余除法)

整数上的带余除法 亦称为 Euclidean 除法 或 除法算法.

命题 11 (整除的余数判据)

设 且 . 则 当且仅当 除以 的 余数 为 .

证明 12 (整除的余数判据)

这是 余数的基本性质 的 (2).

5. 相关概念

• 因数
• 倍数
• 公因数
• 公倍数
• 商
• 余数

6. 术语翻译

中文	英文
整除	divisibility
整除	divides
带余除法	Euclidean division / division algorithm

初等数论