带余除法

欧几里得除法（英語：Euclidean division），也称为带余除法（英語：division with remainder），是数学中的一种基本算术计算方式。给定一个被除数$a$和一个除数$b$，带余除法给出一个整数商$q$和一个介于一定范围的余数$r$，使得下面等式成立：

17个点五个五个排列，可以排3列，剩余两个。用带余除法来说，17除以5等于3，余数是2.

$a=bq+r$

一般所称“欧几里得除法”，限定余数的范围为：

$0\leq r<|b|$

还有叫做“居中除法”（英語：centered division）的变体，限定余数为${\textstyle -{\frac {b}{2}}\leq r<{\frac {b}{2}}}$，这种余数称为“居中余数”。这样的限定都是为了使得满足等式的$q$有且仅有一个。这时候的$q$称为带余除法的商。

概述

最常见的带余除法是整数与整数的带余除法（被除数$a$和除数$b$都是整数），但实数与整数乃至实数与实数的带余除法也有应用。对一般的抽象代数系统，能够进行带余除法的都是具有欧几里得性质的系统。如果余数为零，则称$b\,$整除$\,a$。一般约定除数$b$不能为$0$。

带余除法可表示为：

$a\div b=q\dots r$

表达为：“$a$除以$b$等于$q$，余$r$”。

带余除法的计算有长久的历史，有各种计算工具和计算方法。最常用的是长除法（竖式除法）。带余除法在数论中有不少用途，比如说辗转相除法的基本步骤就是带余除法。术语“欧几里得除法”是在二十世纪期间作为“欧几里得环的除法”的简称而介入的。

例子

如何将30个苹果尽可能地分给7个人，并且使每人一样多？

以下是整数带余除法的例子：依照公历，一年中的四月份有30天。每星期有7天，从四月的第一天开始，可以数出有四个星期，此外还有2天。如果要数出5个星期，则还差了5天。带余除法表示，就是：

$30\div 7=4\dots 2$

里面的30是被除数，7是除数，4是带余除法得到的商，2是带余除法得到的余数。日常生活中说：“四月份有四个多星期”，是带余除法的结果。

另一个例子是分配问题。假设有30个苹果要分给7个人，每人分的要一样多，那么可以使用带余除法：

$30\div 7=4\dots 2$

这说明每人可以分到4个，还剩余2个。如果每人分5个，则是不够的。每人如果只分3个，则还剩余9个，可以继续分。带余除法说明了在人人分到的要一样多的条件下，每人可以分到的最多苹果数目。

不同的带余除法

最基本的带余除法是整数与整数的带余除法，这时商和余数都是整数。实数与整数的带余除法，或实数与实数的带余除法，余数是实数，但不一定是整数。比如说讨论使用正弦函数构造的数列$\{\sin {n}\mid n\in \mathbb {Z} \}$时，就需要使用除数为$2\pi$的带余除法，来讨论每一项具体的取值。

基本定理

带余除法限定了余数的范围，使得商唯一存在。整数与整数的带余除法中，余数的范围通常是$\{0,1,\dots ,|b|-1\}$这样的$b$个元素的集合。被除数为实数的带余除法中，常常会使用介于0和除数$\left\vert b\right\vert$之间（大于等于0，严格小于$\left\vert b\right\vert$）的半开闭区间作为余数的范围；另一种常见的范围是大于等于${\textstyle -{\frac {\left\vert b\right\vert }{2}}}$，严格小于${\textstyle {\frac {\left\vert b\right\vert }{2}}}$。带余除法的基本定理说明：整数与整数的带余除法中，只要余数的范围是$\left\vert b\right\vert$个整数，并且任何两个数之差都不是b的倍数，那么带余除法的商唯一存在；被除数为实数的除法中，只要余数的范围是一个如同长度为$\left\vert b\right\vert$的半开半闭区间，那么带余除法的商唯一存在。

最常见的带余除法中用到的是整数除以整数的一个版本：

对任何给定的整数$a$和非零整数$b$，都存在唯一的整数$q$以及属于集合$\{0,1,\dots ,|b|-1\}$的整数$r$，使得

$a=bq+r$

证明

定理的证明是将整数集合或实数轴分割成长度为|b|的区间段。證明由兩部分組成 - 首先證明$q$和$r$的存在性，其次證明$q$和$r$的唯一性。

整数除以整数的情况：

假设余数的范围是$R=\{r_{1},r_{2},\dots ,r_{|b|}\}$，其中任两个数的差都不是$b$的倍数。那么可以将全体整数分割成以下集合的不交并集：

$\mathbb {Z} =\sqcup _{k\in \mathbb {Z} }\{r_{1}+kb,r_{2}+kb,\dots ,r_{|b|}+kb\}=\sqcup _{k\in \mathbb {Z} }R_{k}$

其中的$\sqcup$指两两不相交的并集。这样的划分方式下，不会有两个集合有交集。反设有两个集合$R_{k}$和$R_{l}$有交集：

$r_{i}+kb=r_{j}+lb$

那么

$r_{i}-r_{j}=(l-k)b$

这说明有两个元素的差是$b$的倍数。矛盾。另一方面，任何一个整数都必然属于某个$R_{k}$。设有整数$s$，那么存在整数$q_{s}$使得$q_{s}b\leq s<q_{s}b+b$，也就是说存在$\{0,1,\dots ,|b|-1\}$里的一个数$t_{s}$，使得$s=q_{s}b+t_{s}$ 同样地，对$r_{1},r_{2},\dots ,r_{|b|}$里的每一个数$r_{i}$，也各自存在$\{0,1,\dots ,|b|-1\}$的一个数$t_{i}$和一个整数$q_{i}$，使得$r_{i}=q_{i}b+t_{i}$ 由于有$b+1$个属于集合$\{0,1,\dots ,|b|-1\}$的整数，根据抽屉原理，必然有两个整数相同。而由前所证，不可能有$t_{i}=t_{j}$的情况，所以只能是存在某个$i$使得$t_{i}=t_{s}$，所以：

$s=q_{s}b+t_{s}=q_{s}b+t_{i}=q_{s}b+r_{i}-q_{i}b$

$s=r_{i}+(q_{s}-q_{i})b\in R_{q_{s}-q_{i}}$

因此，任何一个整数都唯一地属于某个$R_{k}$。而对应的这个整数$k$就是带余除法唯一确定的商。

被除数是实数的情况：

假设余数的范围是$[x,x+b)$，那么将实数轴$\mathbb {R}$分割为：

$\mathbb {R} =\sqcup _{k\in \mathbb {Z} }[x+kb,x+(k+1)b)$

这个分割方式构成了实数的一个分划，每个实数都唯一地属于其中的某一个区间段，所以被除数$a$也必然唯一地属于其中的某一个区间段。假设$a$属于区间段：$I_{q}=[x+q_{0}b,x+(q_{0}+1)b)$，则说明

$x\leq a-q_{0}b<x+b$

所以带余除法的商唯一确定，就是$q_{0}$。

计算

计算带余除法和计算除法的手段基本相同。手工计算时常常使用长除法，与除法不同之处是到个位即停止，剩余的即是余数。计算机运算中使用的带余除法一般耗费的时间比相同位数的乘法更久，所以编程时为了减少机器运算量，常常会尽力避免除法运算。一般的编程语言和数学、统计软件中，带余除法运算符（指令）和取模运算符（指令）可能是分开的，也可能是合并的。如在进行带余除法时尽管默认返回的是商，但实际上余数也储存在运算结果中。除数是2的幂次的时候，可以使用右移的位移运算代替带余除法。这是因为计算机储存数据使用的是二进制，取一个长度为$n$的二进制数的前$k$位，实际上就是它除以2的$n-k$次幂後的商，而後$n-k$位则是其余数。

算法

原始算法

原始的带余除法算法可以视为是重复使用减法的过程。设要计算$a$除以$b$，则在$a$里面不断地扣除$b$，直到不能继续扣除（满足余数范围）为止。以$a$、$b$都是正整数，余数范围为$\{0,1,\dots ,b-1\}$的除法为例，伪代码如下：

function Division(a, b)
    q ← 0; r ← a; 
     while r >= b do
        r ← r - b;
        q ← q + 1;
     end while
     return q, r;

这样的算法复杂度是${\frac {a}{b}}$的级别。

使用二分法

更为优化的算法是使用二进制以及二分法的结合。算法大致分为两个部分：首先用不断倍增的方式找出一个$a$所属的区间，然后用二分法不断收窄区间，直到将$a$限制在一个长度为$b$的区间为止。举例来说，要计算237除以9，可以首先列出如下表格：

0	1	2	3	4	5
1	2	4	8	16	32
9	18	36	72	144	288

也就是从小到大逐个列出2的幂次与9的乘积，直到超过237为止。其中，2⁴ × 9 = 144 是小于等于237的最大数，之後的288就比237更大了。接下来反过来利用2的幂次与9的乘积来计算237除以9。过程如下：

• 设$q=16$，$p=32$；
• 237介于144与288之间，而144和288的平均数是216，比237小，令$q={\frac {16+32}{2}}=24$，$p=32$；
• 216和288的平均数是252，比237大，令$q=24$，$p={\frac {24+32}{2}}=28$；
• 216和252的平均数是234，比237小，令$q={\frac {24+28}{2}}=26$，$p=28$；
• 234和252的平均数是243，比237大，令$q=26$，$p={\frac {26+28}{2}}=27$；
• 最后得到$q$的值为26，这就是237除以9的商，237减去234剩余的3就是余数。伪代码如下：

function QuickDivision(a, b)
     counter ← 0; power ← 1; mid ← 0; appr ← 0;
     //-{zh-hans:找到2的幂次与除数b的乘积中比被除数a大的最小数对应的幂次;zh-hant:找到2的冪次與除數b的乘積中比被除數a大的最小數對應的冪次}-
     while power * b <= a do
        counter ← counter + 1;
        power ← power * 2 ;
     end while
     p ← power; q ← power / 2;
     //p和q乘以b以後分别是a的上界和下界，以下用二分法不断收窄上下界，直到上下界之差等于b（即p与q之差等于1）为止
     for k from 1 to counter - 1 do
        //计算上下界的平均值
        comp ← (p + q) / 2;
        mid ← comp * b;
        //如果平均值小于等于a，则调高下界，同时记录平均值，否则调低上界
        if mid <= a then
           appr ← mid;
           q ← comp;
        else
           p ← comp;
        end if
     end for 
     //结束后q乘以b的积就是小于等于a的b的倍数中最大的，这说明q就是商；appr是最後一个小于等于a的平均值，所以它和a的差就是余数
     r ← a - appr; 
     return q, r;

以上的算法的复杂度在$\log _{2}\left({\frac {a}{b}}\right)$级别，当${\frac {a}{b}}$较大时，远远比原始的算法快捷。

推广

多项式的带余除法

更多信息：多項式長除法

以域$\mathbb {K}$为系数的多项式构成的多项式整环$\mathbb {K} [X]$中也可以定义带余除法。设有$A$、$B$两个多项式，其中$B$不是零多项式。则存在由$A$和$B$唯一确定的多项式$Q$和$R$，使得：

$A=BQ+R$

并且多项式$R$是零多项式或者它的次数严格小于$B$的次数，称为多项式带余除法的余元。

欧几里得整环

主条目：歐幾里得整環

普通的整数或实数之间的带余除法可以良好定义。在更广泛的代数结构中，能够定义带余除法的代数结构被称为欧几里得整环。定义如下：

设有整环$D$和从$D$到自然数的映射$v:D\setminus \{0_{D}\}\to \mathbb {N} \cup \{0\}$，使得：

若$a,b\in D$而$b\neq 0_{D}$，则存在$q,r\in D$使得$a=bq+r$，而且要么有$r=0_{D}$，或者 $v(r)<v(b)$。

则称$D$为欧几里得整环。

欧几里得整环中，使用一个额外的函数来比较两个元素之间的“大小”关系，从而能够定义带余除法。这个函数也称为范数。欧几里得整环必然是主理想整环因而也必然是唯一分解整环。

参见

• 除法
• 同余