欧几里德除法

**帶餘除法**，也稱為**歐幾里德除法**（英語：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 天，從四月的第一天開始，可以數出有四個星期，此外還有 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 $ 的半開半閉區間，那麼帶餘除法的商唯一存在。:25

最常見的帶餘除法中用到的是整數除以整數的一個版本：

### 證明

定理的證明是將整數集合或實數軸分割成長度為 |b| 的區間段。證明由兩部分組成 - 首先證明 $q$ 和 $r$ 的存在性，其次證明 $q$ 和 $r$ 的唯一性。

## 計算

計算帶餘除法和計算除法的手段基本相同。手工計算時常常使用長除法，與除法不同之處是到個位即停止，剩餘的即是餘數。計算機運算中使用的帶餘除法一般耗費的時間比相同位數的乘法更久，所以編程時為了減少機器運算量，常常會盡力避免除法運算。一般的程式語言和數學、統計軟體中，帶餘除法運算符（指令）和取模運算符（指令）可能是分開的，也可能是合併的。如在進行帶餘除法時儘管默認返回的是商，但實際上餘數也儲存在運算結果中。除數是 2 的冪次的時候，可以使用右移的位移運算代替帶餘除法。這是因為計算機儲存數據使用的是二進位，取一個長度為 $n$ 的二進位數的前 $k$ 位，實際上就是它除以 2 的 $n-k$ 次冪後的商，而後 $n-k$ 位則是其餘數。

### 算法

#### 原始算法

原始的帶餘除法算法可以視為是重複使用減法的過程。設要計算 $a$ 除以 $b$ ，則在 $a$ 裡面不斷地扣除 $b$ ，直到不能繼續扣除（滿足餘數範圍）為止。以 $a$ 、 $b$ 都是正整數，餘數範圍為 $\{0,1,\dots ,b-1\}$ 的除法為例，偽代碼如下：

這樣的算法複雜度是 ${\frac {a}{b}}$ 的級別。

#### 使用二分法

更為優化的算法是使用二進位以及二分法的結合。算法大致分為兩個部分：首先用不斷倍增的方式找出一個 $a$ 所屬的區間，然後用二分法不斷收窄區間，直到將 $a$ 限制在一個長度為 $b$ 的區間為止。舉例來說，要計算 237 除以 9，可以首先列出如下表格：

也就是從小到大逐個列出 2 的冪次與 9 的乘積，直到超過 237 為止。其中，24 × 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 就是餘數。偽代碼如下：

以上的算法的複雜度在 $\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$ 的次數，稱為多項式帶餘除法的**餘元**。: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$ 為歐幾里德整環。:141

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

## 參見

* 除法
* 同餘

## 參考來源