取餘運算

**模除**（又稱**模數**、**取模操作**、**取模運算**等，英語：modulo 有時也稱作 modulus）得到的是一個數除以另一個數的餘數。

給定兩個正整數：被除數 $a$ 和除數 $n$ ，_a_ modulo _n_ (縮寫為 $a{\bmod {n}}$ ) 得到的是使用歐幾里德除法時 ${\frac {a}{n}}$ 的餘數。
舉個例子：計算表達式 " $5{\bmod {2}}$ " 得到 1，因為 $5\div 2=2\ldots 1$ （5 除以 2 商 2 餘 1）；而 " $9{\bmod {3}}$ " 得到 0，因為 $9\div 3=3\ldots 0$ ；注意：如果使用計算器做除法，不能整除時，你不會得到商，而是會得到一個小數，如： $5\div 2=2.5$ 。

雖然通常情況下 $a$ 和 $n$ 都是整數，但許多計算系統允許其他類型的數字操作，如：對浮點數取模。一個整數對 $n$ 取模的結果範圍為： 0 到 $n-1$ （ $a{\bmod {1}}$ 恆等於 0； $a{\bmod {0}}$ 則是未定義的，在程式語言里可能會導致除零錯誤）。
有關概念在數論中的應用請參閱模算數。

當 $a$ 和 $n$ 均為負數時，通常的定義就不適用了，不同的程式語言對結果有不同的處理。

## 定義與餘數的計算

在數學中，取模運算的結果就是歐幾里德除法的餘數。當然也有許多其他的定義方式。計算機和計算器有許多種表示和儲存數字的方法，因此在不同的硬體環境下、不同的程式語言中，取模運算有著不同的定義。

幾乎所有的計算系統中， $n$ 除 $a$ 得到商 $q$ 和餘數 $r$ 均滿足以下式子：

　
: :

然而這樣做，當餘數非 0 時，餘數的符號仍然是有歧義的：餘數非 0 時，它的符號有兩種選擇，一個正、一個負。通常情況下，在數論中總是使用正餘數。但在程式語言中，餘數的符號取決於程式語言的類型和被除數 _a_ 或除數 $n$ 的符號。
標準 Pascal 和 ALGOL 68 總是使用 0 或正餘數；另一些程式語言，如 C90 ，當除數 $a$ 和除數 $n$ 都是負數時，C90 標準並沒有做具體的規定，而是留給編譯器去定義並實現。
在大多數系統上 $a{\bmod {0}}$ 時未定義的，雖然有些系統定義它就等於 $a$ 。更多詳情參見表格。

* 很多取模的實現都使用了_截斷除法_，此時商由截斷函數定義定義 $q=\mathrm {trunc} \left({\frac {a}{n}}\right)$ ，因此由等式 **1** 有，餘數_和被除數符號一致_。商向零取整：結果等於普通除法所得的小數靠近 0 方向的第一個整數。

　
: $r=a-n\operatorname {trunc} \left({\frac {a}{n}}\right)$

* 高德納定義的_取底除法_的商由取底函數定義： $q=[{\frac {a}{n}}]$ 。因此由等式 **1** 有，餘數_和除數符號一致_。因為使用了取底函數，商總是向下取整，即使商已經是負數。

　
: $r=a-n\left[{\frac {a}{n}}\right]$

* Raymond T. Boute 使用的歐幾里得定義中，餘數總是非負的 $0\leq r$ ，這與歐幾里得算法是一致的。

在這種情況下：

　
: $n>0\Rightarrow q=\left[{\frac {a}{n}}\right]$

　
: $n<0\Rightarrow q=-\left[-{\frac {a}{n}}\right]$

或者等價的：

　
: $q=\operatorname {sgn}(n)\left[{\frac {a}{\left|n\right|}}\right]$

這裡的 $\mathrm {sgn} $ 是符號函數，因此

　
: $r=a-|n|\left[{\frac {a}{\left|n\right|}}\right]$

* Common Lisp 也定義了自己的捨入除法和進位除法，商分別定義為 $q=\mathrm {round} \left({\frac {a}{n}}\right)$ 和 $q=-\left[{\frac {-a}{n}}\right]$ 。
* IEEE 754 定義了一個取余函數，商被定義為 ${\frac {a}{n}}$ ，依據捨入約定取整。因此餘數的符號選定為_最接近 0_。

 

## 常見錯誤

當取模的結果與被除數符號相同時，可能會導致意想不到的錯誤。

舉個例子：如果需要判斷一個整數是否為奇數，有人可能會測試這個數除 2 的餘數是否為 1：

但在一個取模結果與被除數符號相同的程式語言里，這樣做是錯的。因為當被除數 _n_ 是奇數且為負數時， $n{\bmod {2}}$ 得到 −1，此時函數返回「假」。

一種正確的實現是測試取模結果是否為 0，因為餘數為 0 時沒有符號的問題：

或者考慮餘數的符號，有兩種情況：餘數可能為 1 或 -1。

## 記號

一些計算器有取模 mod() 按鈕，很多程式語言里也有類似的函數，通常像 mod(_a_, _n_) 這樣。
有些語言也支持在表達式內使用 "%"、"mod" 或 "Mod" 作為取模或取余操作符。

　
: `a % n`

或

　
: `a mod n`

或者在一些沒有 mod() 函數的環境中使用等價的：
（注意 'int' 事實上等價於截斷函數 ${\frac {a}{n}}$ ，進行了向 0 取整）

　
: `a - (n * int(a/n))`

## 等價性

一些取模操作，經過分解和展開可以等同於其他數學運算。這在密碼學的證明中十分有用，例如：迪菲 - 赫爾曼密鑰交換。

* 恆等式：
   * $(a{\bmod {n}}){\bmod {n}}=a{\bmod {n}}$
  * 對所有的正數 $x$ 有： $n^{x}{\bmod {n}}=0$
  * 如果 $p$ 是一個質數，且不為 $b$ 的因數，此時由費馬小定理有： $ab^{p-1}{\bmod {p}}=a{\bmod {p}}$
* 逆運算：
   * $[(-a{\bmod {n}})+(a{\bmod {n}})]={\bmod {n}}=0$ .
  * $b^{-1}{\bmod {n}}$ 表示模反元素。若且唯若 $b$ 與 $n$ 互質時，等式左側有定義： $[(b^{-1}{\bmod {n}})(b{\bmod {n}})]{\bmod {n}}=1$ 。
* 分配律：
   * $(a+b){\bmod {n}}=[(a{\bmod {n}})+(b{\bmod {n}})]{\bmod {n}}$
  * $ab{\bmod {n}}=[(a{\bmod {n}})(b{\bmod {n}})]{\bmod {n}}$
  * $d{\bmod {(}}abc)=(d{\bmod {a}})+a[(d\backslash a{\bmod {b}})]+ab[(d\backslash a\backslash b){\bmod {c}}]$ ，符號 \ 是歐幾里德除法中的除法操作符，運算結果為商
  * $c{\bmod {(}}a+b)=(c{\bmod {a}})+[bc\backslash (a+b)]{\bmod {b}}-[bc\backslash (a+b)]{\bmod {a}}$ .
* 除法定義：僅當式子右側有定義時，即 $b$ 、 $n$ 互質時有： ${\frac {a}{b}}{\bmod {n}}=[(a{\bmod {n}})(b^{-1}{\bmod {n}})]{\bmod {n}}$ ，其他情況為未定義的。
* 乘法逆元： $[(ab{\bmod {n}})(b^{-1}{\bmod {n}})]{\bmod {n}}=a{\bmod {n}}$ .

## 性能問題

可以通過依次計算帶餘數的除法實現取模操作。特殊情況下，如某些硬體上，存在更快的實現。
例如：2 的 n 次冪的模，可以通過逐位與運算實現：

　
: `x % 2n == x & (2n - 1)`

例子，假定 _x_ 為正數：

　
: `x % 2 == x & 1`

　
: `x % 4 == x & 3`

　
: `x % 8 == x & 7`

在進行位操作比取模操作效率更高的設備或軟體環境中，以上形式的取模運算速度更快。

編譯器可以自動識別出對 2 的 n 次冪取模的表達式，自動將其優化為 `expression & (constant-1)`。這樣可以在兼顧效率的情況下寫出更整潔的代碼。這個優化在取模結果與被除數符號一致的語言中（包括 C 語言）不能使用，除非被除數是無符號整數。這是因為如果被除數是負數，則結果也是負數，但 `expression & (constant-1)` 總是正數，進行這樣的優化就會導致錯誤，無符號整數則沒有這個問題。

## 用途

* 取模運算可用於判斷一個數是否能被另一個數整除。對 2 取模即可判斷整數的奇偶性；從 2 到 $n-1$ 取模則可判斷一個數是否為質數。
* 進制之間的轉換。
* 用於求取最大公約數的輾轉相除法使用取模運算。
* 密碼學中的應用：從古老的凱撒密碼到現代常用的 RSA、橢圓曲線密碼，它們的實現過程均使用了取模運算。

## 參見

* 模 (消歧義) 和模 (術語) —— 「模數（Modulo）」這個詞的許多用法，都是 1801 年卡爾・弗里德里希・高斯引入模算數時產生的。
* 模冪運算
* 同餘

## 腳註

## 參考文獻