带余除法
| 带余除法 | |
|---|---|
| 术语名称 | 带余除法 |
| 英语名称 | Euclidean division |
| 别名 | 欧几里得除法, 欧氏除法 |
| 被除数 | |
|---|---|
| 术语名称 | 被除数 |
| 英语名称 | dividend |
| 除数 | |
|---|---|
| 术语名称 | 除数 |
| 英语名称 | divisor |
| 商 | |
|---|---|
| 术语名称 | 商 |
| 英语名称 | quotient |
| 别名 | 不完全商, incomplete quotient |
| 余数 | |
|---|---|
| 术语名称 | 余数 |
| 英语名称 | remainder |
带余除法或欧几里得除法(Euclidean division)指对两个整数，计算一个除不尽的“不完全”商和余数的算法。
自然数上也可以定义带余除法。
由于整数上取余数的范围有一定可调整范围，在说带余除法时，有时可能有不同的余数范围定义。
定义
| 带余除法 | |
|---|---|
| 运算名称 | 带余除法 |
| 运算符号 | |
| Latex | |
| 运算对象 | 整数, 非零整数 |
| 运算元数 | 2 |
| 运算结果 | 整数 |
| 定义域 | [math]\displaystyle{ \mathbb{Z}\times\mathbb{Z}^{*} }[/math] |
| 陪域 | [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}) (\exists r \in \mathbb{Z}) (a = b q + r \land 0\leq r \lt |b|) }[/math] ，则可证明 [math]\displaystyle{ q }[/math]、 [math]\displaystyle{ r }[/math] 唯一。此时 [math]\displaystyle{ a }[/math] 和 [math]\displaystyle{ b }[/math] 之间的这种运算，称为整数的带余除法或欧几里得除法(Euclidean division)。类比于除法， [math]\displaystyle{ a }[/math] 称为被除数(dividend)， [math]\displaystyle{ b }[/math] 称为除数(divisor)， [math]\displaystyle{ q }[/math] 称为不完全商(incomplete quotient)或仍称为商(quotient)， [math]\displaystyle{ r }[/math] 称为余数(remainder)。
在自然数上，则定义对应变为 [math]\displaystyle{ (\exists q \in \mathbb{Z}) (\exists r \in \mathbb{Z}) (a = bq+r \land 0\leq r \lt b) }[/math] 。
注： [math]\displaystyle{ r=0 }[/math] 时就是整除。
一般的带余除法
一般地，对整数 [math]\displaystyle{ a \in \mathbb{Z} }[/math] 和非零整数 [math]\displaystyle{ b \in \mathbb{Z}^* }[/math] ，对任意的 [math]\displaystyle{ d\in\mathbb{Z} }[/math] ，必 [math]\displaystyle{ (\exists q \in \mathbb{Z}) (\exists r \in \mathbb{Z}) (a = b q + r \land d \leq r \lt |b| + d) }[/math] ，其中 [math]\displaystyle{ q }[/math]、 [math]\displaystyle{ r }[/math] 唯一。
| 最小非负余数 | |
|---|---|
| 术语名称 | 最小非负余数 |
| 英语名称 | least nonnegative remainder |
| 别名 | 余数, remainder |
| 最小正余数 | |
|---|---|
| 术语名称 | 最小正余数 |
| 英语名称 | least positive remainder |
| 绝对最小余数 | |
|---|---|
| 术语名称 | 绝对最小余数 |
| 英语名称 | least absolute remainder |
将任意 [math]\displaystyle{ d }[/math] 时的 [math]\displaystyle{ r }[/math] 统称为余数(remainder)。特别地：
- 上述 [math]\displaystyle{ 0 \leq r \lt |b| }[/math] 即 [math]\displaystyle{ d=0 }[/math] 的情况，称为最小非负余数(least nonnegative remainder)，通常直接称为余数(remainder)；
- 若 [math]\displaystyle{ 0 \lt r \leq |b| }[/math] 即 [math]\displaystyle{ d=1 }[/math] ，称为最小正余数(least positive remainder)；
- 若 [math]\displaystyle{ -\tfrac{|b|}{2} \leq r \lt \tfrac{|b|}{2} }[/math] 或 [math]\displaystyle{ -\tfrac{|b|}{2} \lt r \leq \tfrac{|b|}{2} }[/math] ，称为绝对最小余数(least absolute remainder)。
注：利用取整函数，也可以通过有理数上的除法定义为 [math]\displaystyle{ q = \lfloor \frac{a}{b} \rfloor, r = a - b q }[/math] 。
性质
有 [math]\displaystyle{ \operatorname{gcd}(a, b) = \operatorname{gcd}(b, r) }[/math] 。
由于余数取值有限，往往可以通过抽屉原理证明其中有相等的情况。
- 奇数 [math]\displaystyle{ a \gt 2 }[/math] 有 [math]\displaystyle{ (\exists d \lt a)(a \mid 2^d - 1) }[/math] ，且满足这一条件的最小 [math]\displaystyle{ d_0 }[/math] ，有 [math]\displaystyle{ (\forall h\in \mathbb{N})(a \mid 2^h - 1 \leftrightarrow d_0 \mid h) }[/math] 。
| 整除理论 | ||
|---|---|---|
| 整除关系 | 整除、倍数、因数 | 带余除法 |
| 正整数的分类 | 1、质数、合数 | |
| 质数测试 | 试除法、埃氏筛、线性筛 | |
| 最大公约数理论 | 公倍数、最小公倍数 [math]\displaystyle{ \operatorname{lcm} }[/math]、公因数、最大公因数 [math]\displaystyle{ \operatorname{gcd} }[/math] | 辗转相除法 |
| 互质 | ||
| 算术基本定理 | 算术基本定理 | 标准质因数分解 |