帶餘除法

歐幾里得除法（英語：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$為歐幾里得整環。

歐幾里得整環中，使用一個額外的函數來比較兩個元素之間的「大小」關係，從而能夠定義帶餘除法。這個函數也稱為範數。歐幾里得整環必然是主理想整環因而也必然是唯一分解整環。

參見

• 除法
• 同餘