整除关系
| 整除 | |
|---|---|
| 术语名称 | 整除 |
| 英语名称 | |
| 倍数 | |
|---|---|
| 术语名称 | 倍数 |
| 英语名称 | multiple |
| 因数 | |
|---|---|
| 术语名称 | 因数 |
| 英语名称 | divisor |
| 别名 | factor, 约数 |
整除关系(divisor)指对两个整数，相除能得到整数的商；或者说其中一个整数能被表示为另一个数和某个整数之积。
自然数上也可以定义整除。
定义
| 整除 | |
|---|---|
| 关系名称 | 整除 |
| 关系符号 | [math]\displaystyle{ \mid }[/math] |
| Latex | \mid
|
| 关系对象 | 非零整数, 整数 |
| 关系元数 | 2 |
| 类型 | 偏序 |
| 全集 | [math]\displaystyle{ \mathbb{Z}^{*}\times\mathbb{Z} }[/math] |
对整数 [math]\displaystyle{ a \in \mathbb{Z} }[/math] 和非零整数 [math]\displaystyle{ b \in \mathbb{Z}^* }[/math] ，若 [math]\displaystyle{ (\exists q \in \mathbb{Z})(a = bq) }[/math] ，则称 [math]\displaystyle{ b }[/math] 整除 [math]\displaystyle{ a }[/math] ([math]\displaystyle{ b }[/math] (evenly) divides [math]\displaystyle{ a }[/math]) ，或称 [math]\displaystyle{ a }[/math] 被 [math]\displaystyle{ b }[/math] 整除 ([math]\displaystyle{ a }[/math] is (evenly) divisible by [math]\displaystyle{ b }[/math])，记作 [math]\displaystyle{ b \mid a }[/math] 。此时称 [math]\displaystyle{ b }[/math] 是 [math]\displaystyle{ a }[/math] 的因数(divisor/factor)， [math]\displaystyle{ a }[/math] 是 [math]\displaystyle{ b }[/math] 的倍数(multiple)。
注：“被……整除”的顺序和通常的“被/以……除”两个数的顺序是相同的。由于整除常用主动形式的“整除”，除法常用被动形式的“除以”，表达上会有一些差异。
注：有的定义中不要求 [math]\displaystyle{ b }[/math] 非零。
相反的情况，称为 [math]\displaystyle{ b }[/math] 不（能）整除 [math]\displaystyle{ a }[/math] ([math]\displaystyle{ b }[/math] does not (evenly) divide [math]\displaystyle{ a }[/math]) ，或称 [math]\displaystyle{ a }[/math] 不（能）被 [math]\displaystyle{ b }[/math] 整除 ([math]\displaystyle{ a }[/math] is not (evenly) divisible by [math]\displaystyle{ b }[/math])，记作 [math]\displaystyle{ b \not\mid a }[/math] 。
整数 [math]\displaystyle{ n }[/math] 的倍数所构成的集合，可以使用陪集记号记作 [math]\displaystyle{ n\mathbb{Z} }[/math] 。
性质
| 平凡因数 | |
|---|---|
| 术语名称 | 平凡因数 |
| 英语名称 | trivial divisor |
| 别名 | trivial factor, 显然因数 |
| 非平凡因数 | |
|---|---|
| 术语名称 | 非平凡因数 |
| 英语名称 | non-trivial divisors |
| 别名 | non-trivial factors, 非显然因数 |
- 0 是任意（非零）整数的倍数。
- 定义在正整数、自然数、某个数的因数集时，整除是一种偏序：
- 自反：任意一个整数 [math]\displaystyle{ a }[/math] 有 [math]\displaystyle{ a\mid a }[/math] 。
- 对称：任意两个整数 [math]\displaystyle{ a \mid b \land b \mid a \rightarrow a = b }[/math] 。
- 在非零整数或全体整数上时 [math]\displaystyle{ a \mid b \land b \mid a \rightarrow a = b \lor a = -b }[/math] 。
- 传递：任意三个整数 [math]\displaystyle{ a \mid b \land b \mid c \rightarrow a \mid c }[/math] 。
- 对整数 [math]\displaystyle{ b }[/math] ，有 [math]\displaystyle{ 1, -1, b, -b }[/math] 四个数一定是其因数；自然数中则有 [math]\displaystyle{ 1, b }[/math] 是其因数。每个这样的因数称为其一个平凡因数(trivial divisor)，一个不是平凡因数的因数称为其一个非平凡因数(non-trivial/strict divisor)。
- 对正整数，与自身不等的因数也叫做真因数(proper divisor/aliquot part)，与自身不等的非因数也称为 aliquant part 。
- 对整数 [math]\displaystyle{ a }[/math] ，若 [math]\displaystyle{ d }[/math] 取遍 [math]\displaystyle{ a }[/math] 的全部因数，同时 [math]\displaystyle{ a/d }[/math] 也一定取遍 [math]\displaystyle{ a }[/math] 的全部因数。
| 整除理论 | ||
|---|---|---|
| 整除关系 | 整除、倍数、因数 | 带余除法 |
| 正整数的分类 | 1、质数、合数 | |
| 质数测试 | 试除法、埃氏筛、线性筛 | |
| 最大公约数理论 | 公倍数、最小公倍数 [math]\displaystyle{ \operatorname{lcm} }[/math]、公因数、最大公因数 [math]\displaystyle{ \operatorname{gcd} }[/math] | 辗转相除法 |
| 互质 | ||
| 算术基本定理 | 算术基本定理 | 标准质因数分解 |