?余除法

?余除法 ，也?? ??里德除法 （英語： Euclidean division ）是 ?? 中的一?基本算? ?算方式。?定一?被除? $a$ 和一?除? $b$ ，?余除法?出一?整? $q$ 和一?介于一定范?的余? $r$ ，使得下面等式成立：

a=bq+r

一般所?“??里德除法”，限定余?的范?在0? $b$ 之?。?有叫做“居中除法”的??，限定余?在 $-{\frac {b}{2}}$ ? ${\frac {b}{2}}$ 之?，??余???“居中余?”。??的限定都是?了使得?足等式的 $q$ 有且?有一?。??候的 $q$ ???余除法的商。?余除法一般表示?：

a\div b=q\dots r

表??：“ $a$ 除以 $b$ 等于 $q$ ，余 $r$ ”。最常?的?余除法是整??整?的?余除法（被除? $a$ 和除? $b$ 都是整?），但???整?乃至?????的?余除法也有?用。?一般的抽象代?系?，能??行?余除法的都是具有 ??里德性? 的系?。如果余??零，?? $b$ 整除 $a$ 。一般?定除? $b$ 不能?0。

?余除法的?算有?久的?史，有各??算工具和?算方法。最常用的是 ?除法（?式除法）。?余除法在??中有不少用途，比如? ??相除法的基本步?就是?余除法。

例子 [ ?? ]

如何?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$ ）的半?? ?? 作?余?的范?；?一?常?的范?是大于等于 $-{\frac {\left\vert b\right\vert }{2}}$ ，?格小于 ${\frac {\left\vert b\right\vert }{2}}$ 。?余除法的基本定理?明：整??整?的?余除法中，只要余?的范?是 $\left\vert b\right\vert$ ?整?，?且任何???之差都不是 $b$ 的倍?，那??余除法的商唯一存在；被除????的除法中，只要余?的范?是一?如同?度? $\left\vert b\right\vert$ 的半?半???，那??余除法的商唯一存在。 ^[1]^:
25

最常?的?余除法中用到的是整?除以整?的一?版本：

?任何?定的整? $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$ 就是?余除法唯一?定的商。 ^[2]^:
18-22

被除?是??的情? ：

假?余?的范?是 $[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}}$ 的??。 ^[3]

使用二分法 [ ?? ]

更??化的算法是使用二?制以及二分法的?合。算法大致分???部分：首先用不?倍增的方式?出一? $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}}$ ?大?，??比原始的算法快捷。 ^[3]

推? [ ?? ]

多?式的?余除法 [ ?? ]

以域 $\mathbb {K}$ ?系?的多?式 ?成的多?式整? $\mathbb {K} [X]$ 中也可以定??余除法。?有 $A$ 、 $B$ ??多?式，其中 $B$ 不是零多?式。?存在由 $A$ 和 $B$ 唯一?定的多?式 $Q$ 和 $R$ ，使得：

A=BQ+R

?且多?式 $R$ 是零多?式或者?的次??格小于 $B$ 的次?，??多?式?余除法的余元。 ^[4]^:
10

??里德整? [ ?? ]

普通的整?或??之?的?余除法可以良好定?。在更?泛的代???中，能?定??余除法的代???被????里德整?。定?如下：

?有整?

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

???里德整?。 ^[1]^:
141

??里德整?中，使用一??外的函??比???元素之?的“大小”?系，?而能?定??余除法。??函?也??范?。??里德整?必然是主理想整? 因而也必然是唯一分解整? 。 ^[1]^:
141^[4]^:
16-17

?? [ ?? ]

?考?源 [ ?? ]

^ ^1.0 ^1.1 ^1.2 胡冠章, 王殿?. ?用近世代?. 北京: ??大?出版社. 2006. ISBN 9787302125662 .
^ David M. Burton. Elementary Number Theory. McGraw-Hill. 2010. ISBN 9780073383149 （英?） .
^ ^3.0 ^3.1 Christian Blanchet. Division euclidienne et consequences (PDF) . Groupes et arithmetique, chapitre 1. Universite Paris 7. [ 2013-11-18 ] . （原始?容存? (PDF) 于2011-02-06）（法?） .
^ ^4.0 ^4.1 ??科, ?甫?. 高等代??. 北京: ??大?出版社. 2004. ISBN 9787302082279 .

[hw-1] 1.0 ^1.1 ^1.2 胡冠章, 王殿?. ?用近世代?. 北京: ??大?出版社. 2006. ISBN 9787302125662 .

[burton-2] David M. Burton. Elementary Number Theory. McGraw-Hill. 2010. ISBN 9780073383149 （英?） .

[cb-3] 3.0 ^3.1 Christian Blanchet. Division euclidienne et consequences (PDF) . Groupes et arithmetique, chapitre 1. Universite Paris 7. [ 2013-11-18 ] . （原始?容存? (PDF) 于2011-02-06）（法?） .

[zx-4] 4.0 ^4.1 ??科, ?甫?. 高等代??. 北京: ??大?出版社. 2004. ISBN 9787302082279 .

[1]

[2]

[3]

[4]