带余除法是将整数 分解为非零整数 的整数倍与一个余数之和:
整数 和 分别称为商和余数。对于每一组符合条件的 ,商和余数都存在且唯一。这一结论通常称为带余除法定理,是算术和数论中的基本定理。其英文传统名称虽含有“算法”一词,但该定理描述的是除法结果,而不是计算这一结果的具体步骤。
定义与示例
在等式 中, 是被除数, 是除数。记号 表示除数的绝对值。对余数的限制至关重要:没有这一限制,就会有多组整数 满足同一个等式。
例如,
因此, 除以 ,商为 ,余数为 。虽然 也成立,但它不是带余除法,因为 不小于 。
这一定义也适用于被除数或除数为负数的情况:
| 被除数 | 除数 | 商 | 余数 |
|---|---|---|---|
特别地,
而不能采用余数为负的表达式 。
当 时,除法恰好除尽,即 整除 。当 时,对于任意非零除数,商和余数都为零。除数不能为零,因为在 时,条件 不可能成立。
存在性与唯一性
这一定理包含两个不同的部分:满足条件的一组 总是存在,并且不存在另一组满足相同要求的数。
存在性
先设 。考虑所有形如
的非负整数所组成的集合。这个集合非空,因为当 取足够小的负整数时, 就是非负的。由非负整数的良序性,该集合有最小元素 。将其写为
其中 是相应的整数。
若 ,则
也是同一集合中的非负元素,且比 更小,产生矛盾。因此 ,符合要求。
若 ,则对 应用除数为正的情形:
由于 ,取 即得 。
唯一性
假设有两种分解都满足规定的条件:
相减可得
右侧的绝对值小于 ,而 的任何非零整数倍的绝对值都至少为 。因此,两侧必定都为零。于是 ,且 。
这一数学证明说明了为什么既要限制余数的范围,也要排除除数为零的情况。
与普通除法及取整的关系
当除数 为正时,商是普通除法所得商的向下取整值:
这里,实数的向下取整值是指不大于该数的最大整数。当除数为负时,
其中,向上取整值是指不小于所取数值的最小整数。
带余除法不同于有理数中的除法。普通除法保留完整的数值 ,而带余除法将其分为整数商和余数两部分:
当 为正时, 大于或等于 ,且小于 。
计算
对于非负被除数和正除数,反复相减是一种简单的计算方法:从 开始不断减去 ,直到剩下的数小于 。相减的次数就是商。这种方法虽然正确,但在商很大时效率较低。
长除法则按位处理以位值制记数法表示的数。每一步都将部分被除数除以除数,得到商的一位和一个更小的余数。二进制长除法对二进制数位采用同样的原理。
计算机的具体实现会根据操作数的大小和硬件条件采用不同的算法。对于大整数,高效的除法可以利用近似计算和快速乘法,再通过校正步骤确保所得商和余数精确满足要求。
编程语言中的约定
名为“整数除法”“求余”或“取模”的运算,在操作数为负时不一定采用带余除法的规则。
通常区分以下三种约定:
- **欧几里得除法:**余数满足 。
- **截断除法:**商向零取整;非零余数与被除数同号。
- **向下取整除法:**商向负无穷取整;非零余数与除数同号。
例如,当被除数为 、除数为 时,截断除法得到商 、余数 ,而欧几里得除法得到商 、余数 。除数为正时,向下取整除法与欧几里得除法一致;除数为负时,两者则未必一致。
这些区别在索引、周期性计算以及数论算法的实现中十分重要。浮点运算还涉及另外的舍入问题,不能认为仅对浮点商进行取整就能得到精确的整数除法结果。
在数论中的应用
模算术
对于正整数 ,带余除法为每个整数确定了唯一的余数,其取值为
这为模算术中的每个等价类提供了一个标准代表元。两个整数的余数相同,当且仅当它们的差能被 整除:
代表元是一个普通整数,而同余类则包含无穷多个整数。区分这两类对象,有助于厘清求余数与进行同余运算之间的差别。
最大公约数
若 ,则
事实上,一个整数同时整除 和 ,当且仅当它同时整除 和 。
因此,反复进行带余除法是求最大公约数的欧几里得算法的基础。当除数为正时,依次得到的非零余数严格递减,所以这一过程必然终止。最后一个非零余数就是最大公约数。
“欧几里得除法”这一名称,将带余除法与欧几里得的算术方法联系起来;这些方法记载于《几何原本》。
数的进位表示
反复除以整数基数 ,可以得到一个非负整数的各位数字。每次的余数都在 到 之间;所得数字按从最低位到最高位的顺序依次出现。例如,反复除以 就能得到十进制的各位数字。
多项式除法与代数推广
对于域(数学)上的多项式,也有类似的定理。给定多项式 和非零多项式 ,存在唯一的多项式 和 ,使得
其中,要么 ,要么
这里,多项式的次数取代了整数余数的大小限制。系数构成域,保证了可以除以 的首项系数,从而逐次消去首项。
系数构成域这一假设很重要。在要求系数为整数时,未必能对任意多项式进行这样的除法。例如, 除以 ,若要使余式的次数小于一,商就必须是 。不过,如果除式是首一多项式,那么在任意有单位元的交换系数环上都可以进行这样的除法。
在抽象代数中,欧几里得整环是指在非零元素上配有一个衡量大小的函数的整环;借助这个函数,可以进行带余除法,使余数的大小小于除数,或使余数为零。整数环和域上的多项式环是典型例子。在一般的欧几里得整环中,大小条件未必能保证商和余数唯一;唯一性是常见的整数和多项式情形所具有的额外性质。