带余除法

带余除法
术语名称	带余除法
英语名称	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] 时就是整除的带余除法定义。带余除法必须要求除数不为 0 ，因此与整除的乘法定义转换时必须单独讨论边界条件。

一般的带余除法

一般地，对整数 [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) }[/math] 的存在情况。通常要求约定 [math]\displaystyle{ r }[/math] 的取值范围使得 [math]\displaystyle{ q,r }[/math] 的取值唯一。常见余数范围为对任意的 [math]\displaystyle{ d\in\mathbb{Z} }[/math] 给定余数范围 [math]\displaystyle{ d \leq r \lt |b| + d }[/math] 或 [math]\displaystyle{ d \lt r \lt |b| + d }[/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 = \operatorname{sgn}(b) \left\lfloor \frac{a}{b} \right\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\in\mathbb{N}^*)(d \lt a \land 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、质数、合数
	质数测试	试除法、 Fermat 测试	Eratosthenes 筛法、 Euler 筛法
最大公约数理论	公倍数、最小公倍数 [math]\displaystyle{ \operatorname{lcm} }[/math]、公因数、最大公因数 [math]\displaystyle{ \operatorname{gcd} }[/math]		辗转相除法
	互质
算术基本定理	算术基本定理		标准质因数分解