帶餘除法

<image>

歐幾里得除法（Euclidean division），也稱為帶餘除法（division with remainder），是數學中的一種基本算術計算方式。給定一個被除數$a$和一個除數$b$，帶餘除法給出一個整數商$q$和一個介於一定範圍的餘數$r$，使得下面等式成立：

$$a = bq + r$$

一般所稱「歐幾里得除法」，限定餘數的範圍為：

$$0 \le r < |b|$$

還有叫做「居中除法」（centered division）的變體，限定餘數為$- \frac{b}{2} \le r < \frac{b}{2}$，這種餘數稱為「居中餘數」。這樣的限定都是為了使得滿足等式的$q$有且僅有一個。這時候的$q$稱為帶餘除法的商。

## 概述

最常見的帶餘除法是整數與整數的帶餘除法（被除數$a$和除數$b$都是整數），但實數與整數乃至實數與實數的帶餘除法也有應用。對一般的抽象代數系統，能夠進行帶餘除法的都是具有歐幾里得性質的系統。如果餘數為零，則稱$b\,$整除$\,a$。一般約定除數$b$不能為$0$。

帶餘除法可表示為：

$$a \div b = q \dots r$$

表達為：「$a$除以$b$等於$q$，余$r$」。

帶餘除法的計算有長久的歷史，有各種計算工具和計算方法。最常用的是長除法（豎式除法）。帶餘除法在數論中有不少用途，比如說輾轉相除法的基本步驟就是帶餘除法。術語「歐幾里得除法」是在二十世紀期間作為「歐幾里得環的除法」的簡稱而介入的。

## 例子

<image>

以下是整數帶餘除法的例子：依照公曆，一年中的四月份有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$的半開半閉區間，那麼帶餘除法的商唯一存在。

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

對任何給定的整數$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_0b, x+(q_0+1)b)$，則說明

$$x \le 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\}$的除法為例，偽代碼如下：

```c
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，可以首先列出如下表格：

```
{| class="wikitable" 
```

1

2

4

8

16

32

9

18

36

72

144

288

也就是從小到大逐個列出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就是餘數。偽代碼如下：

```c
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 \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$為歐幾里得整環。

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