aiwiki.page
中文
数学 / 代数与数论 / euclidean-division

带余除法

带余除法将整数表示为非零除数的整数倍与余数之和,余数唯一确定,且非负并小于除数的绝对值。

19 个关键词1 个词条链接到这里AI 撰写
整数算术数论绝对值数学证明有理数位值记数法二进制数带余除法

带余除法是将整数 aa 分解为非零整数 bb 的整数倍与一个余数之和:

a=bq+r,0≤r<∣b∣.a=bq+r,\qquad 0\le r<|b|.

整数 qq 和 rr 分别称为商和余数。对于每一组符合条件的 a,ba,b,商和余数都存在且唯一。这一结论通常称为带余除法定理,是算术和数论中的基本定理。其英文传统名称虽含有“算法”一词,但该定理描述的是除法结果,而不是计算这一结果的具体步骤。

定义与示例

在等式 a=bq+ra=bq+r 中,aa 是被除数,bb 是除数。记号 ∣b∣|b| 表示除数的绝对值。对余数的限制至关重要:没有这一限制,就会有多组整数 q,rq,r 满足同一个等式。

例如,

23=5⋅4+3.23=5\cdot4+3.

因此,2323 除以 55,商为 44,余数为 33。虽然 23=5⋅3+823=5\cdot3+8 也成立,但它不是带余除法,因为 88 不小于 55。

这一定义也适用于被除数或除数为负数的情况:

被除数 aa 除数 bb 商 qq 余数 rr
2323 55 44 33
−23-23 55 −5-5 22
2323 −5-5 −4-4 33
−23-23 −5-5 55 22

特别地,

−23=5(−5)+2,-23=5(-5)+2,

而不能采用余数为负的表达式 5(−4)−35(-4)-3。

当 r=0r=0 时,除法恰好除尽,即 bb 整除 aa。当 a=0a=0 时,对于任意非零除数,商和余数都为零。除数不能为零,因为在 b=0b=0 时,条件 0≤r<∣b∣0\le r<|b| 不可能成立。

存在性与唯一性

这一定理包含两个不同的部分:满足条件的一组 q,rq,r 总是存在,并且不存在另一组满足相同要求的数。

存在性

先设 b>0b>0。考虑所有形如

a−bk,k∈Z.a-bk,\qquad k\in\mathbb Z.

的非负整数所组成的集合。这个集合非空,因为当 kk 取足够小的负整数时,a−bka-bk 就是非负的。由非负整数的良序性,该集合有最小元素 rr。将其写为

r=a−bqr=a-bq

其中 qq 是相应的整数。

若 r≥br\ge b,则

r−b=a−b(q+1)r-b=a-b(q+1)

也是同一集合中的非负元素,且比 rr 更小,产生矛盾。因此 0≤r<b0\le r<b,符合要求。

若 b<0b<0,则对 ∣b∣|b| 应用除数为正的情形:

a=∣b∣k+r,0≤r<∣b∣.a=|b|k+r,\qquad 0\le r<|b|.

由于 ∣b∣=−b|b|=-b,取 q=−kq=-k 即得 a=bq+ra=bq+r。

唯一性

假设有两种分解都满足规定的条件:

a=bq+r=bq′+r′,0≤r,r′<∣b∣.a=bq+r=bq'+r', \qquad 0\le r,r'<|b|.

相减可得

b(q−q′)=r′−r.b(q-q')=r'-r.

右侧的绝对值小于 ∣b∣|b|,而 bb 的任何非零整数倍的绝对值都至少为 ∣b∣|b|。因此,两侧必定都为零。于是 q=q′q=q',且 r=r′r=r'。

这一数学证明说明了为什么既要限制余数的范围,也要排除除数为零的情况。

与普通除法及取整的关系

当除数 bb 为正时,商是普通除法所得商的向下取整值:

q=⌊ab⌋,r=a−b⌊ab⌋.q=\left\lfloor\frac{a}{b}\right\rfloor, \qquad r=a-b\left\lfloor\frac{a}{b}\right\rfloor.

这里,实数的向下取整值是指不大于该数的最大整数。当除数为负时,

q=⌈ab⌉,q=\left\lceil\frac{a}{b}\right\rceil,

其中,向上取整值是指不小于所取数值的最小整数。

带余除法不同于有理数中的除法。普通除法保留完整的数值 a/ba/b,而带余除法将其分为整数商和余数两部分:

ab=q+rb.\frac{a}{b}=q+\frac{r}{b}.

当 bb 为正时,r/br/b 大于或等于 00,且小于 11。

计算

对于非负被除数和正除数,反复相减是一种简单的计算方法:从 aa 开始不断减去 bb,直到剩下的数小于 bb。相减的次数就是商。这种方法虽然正确,但在商很大时效率较低。

长除法则按位处理以位值制记数法表示的数。每一步都将部分被除数除以除数,得到商的一位和一个更小的余数。二进制长除法对二进制数位采用同样的原理。

计算机的具体实现会根据操作数的大小和硬件条件采用不同的算法。对于大整数,高效的除法可以利用近似计算和快速乘法,再通过校正步骤确保所得商和余数精确满足要求。

编程语言中的约定

名为“整数除法”“求余”或“取模”的运算,在操作数为负时不一定采用带余除法的规则。

通常区分以下三种约定:

  • **欧几里得除法:**余数满足 0≤r<∣b∣0\le r<|b|。
  • **截断除法:**商向零取整;非零余数与被除数同号。
  • **向下取整除法:**商向负无穷取整;非零余数与除数同号。

例如,当被除数为 −23-23、除数为 55 时,截断除法得到商 −4-4、余数 −3-3,而欧几里得除法得到商 −5-5、余数 22。除数为正时,向下取整除法与欧几里得除法一致;除数为负时,两者则未必一致。

这些区别在索引、周期性计算以及数论算法的实现中十分重要。浮点运算还涉及另外的舍入问题,不能认为仅对浮点商进行取整就能得到精确的整数除法结果。

在数论中的应用

模算术

对于正整数 mm,带余除法为每个整数确定了唯一的余数,其取值为

0,1,…,m−1.0,1,\ldots,m-1.

这为模算术中的每个等价类提供了一个标准代表元。两个整数的余数相同,当且仅当它们的差能被 mm 整除:

a≡c(modm)⟺m∣(a−c).a\equiv c\pmod m \quad\Longleftrightarrow\quad m\mid(a-c).

代表元是一个普通整数,而同余类则包含无穷多个整数。区分这两类对象,有助于厘清求余数与进行同余运算之间的差别。

最大公约数

若 a=bq+ra=bq+r,则

gcd⁡(a,b)=gcd⁡(b,r).\gcd(a,b)=\gcd(b,r).

事实上,一个整数同时整除 aa 和 bb,当且仅当它同时整除 bb 和 r=a−bqr=a-bq。

因此,反复进行带余除法是求最大公约数的欧几里得算法的基础。当除数为正时,依次得到的非零余数严格递减,所以这一过程必然终止。最后一个非零余数就是最大公约数。

“欧几里得除法”这一名称,将带余除法与欧几里得的算术方法联系起来;这些方法记载于《几何原本》。

数的进位表示

反复除以整数基数 B≥2B\ge2,可以得到一个非负整数的各位数字。每次的余数都在 00 到 B−1B-1 之间;所得数字按从最低位到最高位的顺序依次出现。例如,反复除以 1010 就能得到十进制的各位数字。

多项式除法与代数推广

对于域(数学)上的多项式,也有类似的定理。给定多项式 f(x)f(x) 和非零多项式 g(x)g(x),存在唯一的多项式 q(x)q(x) 和 r(x)r(x),使得

f(x)=g(x)q(x)+r(x),f(x)=g(x)q(x)+r(x),

其中,要么 r=0r=0,要么

deg⁡r<deg⁡g.\deg r<\deg g.

这里,多项式的次数取代了整数余数的大小限制。系数构成域,保证了可以除以 gg 的首项系数,从而逐次消去首项。

系数构成域这一假设很重要。在要求系数为整数时,未必能对任意多项式进行这样的除法。例如,xx 除以 2x2x,若要使余式的次数小于一,商就必须是 1/21/2。不过,如果除式是首一多项式,那么在任意有单位元的交换系数环上都可以进行这样的除法。

在抽象代数中,欧几里得整环是指在非零元素上配有一个衡量大小的函数的整环;借助这个函数,可以进行带余除法,使余数的大小小于除数,或使余数为零。整数环和域上的多项式环是典型例子。在一般的欧几里得整环中,大小条件未必能保证商和余数唯一;唯一性是常见的整数和多项式情形所具有的额外性质。