带余除法

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

${\displaystyle 30\div 7=4\dots 2}$ 

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

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

${\displaystyle 30\div 7=4\dots 2}$ 

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

不同的带余除法

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

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

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

证明

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

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

算法

原始算法

原始的带余除法算法可以视为是重复使用减法的过程。设要计算${\displaystyle a}$ 除以${\displaystyle b}$ ，则在${\displaystyle a}$ 里面不断地扣除${\displaystyle b}$ ，直到不能继续扣除（满足余数范围）为止。以${\displaystyle a}$ 、${\displaystyle b}$ 都是正整数，余数范围为${\displaystyle \{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;

这样的算法复杂度是${\displaystyle {\frac {a}{b}}}$ 的级别。^[3]

使用二分法

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

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

• 设${\displaystyle q=16}$ ，${\displaystyle p=32}$ ；
• 237介于144与288之间，而144和288的平均数是216，比237小，令${\displaystyle q={\frac {16+32}{2}}=24}$ ，${\displaystyle p=32}$ ；
• 216和288的平均数是252，比237大，令${\displaystyle q=24}$ ，${\displaystyle p={\frac {24+32}{2}}=28}$ ；
• 216和252的平均数是234，比237小，令${\displaystyle q={\frac {24+28}{2}}=26}$ ，${\displaystyle p=28}$ ；
• 234和252的平均数是243，比237大，令${\displaystyle q=26}$ ，${\displaystyle p={\frac {26+28}{2}}=27}$ ；
• 最后得到${\displaystyle 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;

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

多项式的带余除法

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

${\displaystyle A=BQ+R}$ 

并且多项式${\displaystyle R}$ 是零多项式或者它的次数严格小于${\displaystyle B}$ 的次数，称为多项式带余除法的余元。^[4]:10

欧几里德整环

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

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

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

则称${\displaystyle D}$ 为欧几里德整环。^[1]:141

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

• 除法
• 同余