模除

<image>

模除（modulo），又稱模算術、取模、取模運算等，它得出一個數除以另一個數的餘數。給定兩個正數：被除數 $a$ 和除數 $n$ (有時也稱作模數，英文寫作modulus)，$a \,\operatorname{modulo}\, n$（通常縮寫為$a \bmod n$），得到的是使用歐幾里得除法時的餘數。$a \bmod 1$所得之數被稱為$a$的小數部份。

舉個例子：計算表達式$5\bmod 2$得到$1$，因為$5\div 2$的商為$2$而餘數為$1$；而$9\bmod 3$得到$0$，因為$9\div 3$的商為$3$而餘數為$0$；做除法不能整除時得到是有理數，平常使用的計算器採用了有限個數位的十進位表示法，它以小數點分隔整數部份和小數部份，比如$5\div 2=2.5$。

雖然通常情況下模除的被除數$a$和除數$n$都是整數，但許多計算系統允許其他類型的數值運算，比如對浮點數取模。在所有計算系統中當被除數$a$和除數$n$都是正數時，結果的餘數$r$的範圍為$0 \le r < n$；而$a \bmod 0$經常是未定義的，在程式語言里可能會導致除以零錯誤。當被除數$a$或除數$n$為負數時，不同的程式語言對結果有不同的處理。

## 各種定義

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

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

$$\begin{align} &q \in \mathbb{Z} \\ &a = n q + r \\ &|r| < |n| \end{align}$$

即使如此，當餘數非$0$時，餘數的符號仍然是有歧義的：餘數非$0$時，它的符號有兩種選擇，一個是正號而另一個是負號。通常情況下，在數論中總是選擇正餘數。但在編程中，選擇餘數的符號依賴於程式語言和被除數$a$或除數$n$的符號。在程式語言所定義的整數模除中，ISO/IEC標準Pascal和ALGOL 68，在計算出的餘數`r`為負數時，返回正數$r + |n|$作為結果；另一些程式語言如ISO/IEC C90，當被除數$a$或除數$n$是負數時，C90標準並沒有做具體的規定，而是留給編譯器去定義並實現

```c
#include <stdio.h>

int main(void)
{
int x = -1,
y = +3;
if ((x%y > 0) ||
    ((x+y)%y == x%y))
    printf("This is a C90 translator behaving differently than C99\n");
}
```

在大多數系統中$a \bmod 0$是未定義的，雖然有些系統定義它就等於$a$。更多詳情參見後續章節表格。

很多取模的實現都使用了「截斷除法」（truncated division），商經由截尾函數來定義，商向零取整，結果等於普通除法所得的小數靠近$0$方向的第一個整數：

$$q=\operatorname{trunc} \left ( \frac{a}{n} \right )$$

餘數和被除數符號一致：

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

高德納定義的「下取整除法」（floored division）

$x$

$\left\lfloor x \right\rfloor$

$x$

$x$

$\left\lceil x \right\rceil$

$x$

$x$

$\left\lceil x \right\rceil = \left\lfloor x \right\rfloor$

$x$

$\left\lceil x \right\rceil = \left\lfloor x \right\rfloor + 1$

$x$

$\left\lfloor -x \right\rfloor = -\left\lceil x \right\rceil$

$x - 1 < \left\lfloor x \right\rfloor \le x \le \left\lceil x \right\rceil < x + 1$

$x$

$y$

$x \bmod y = x - y \left\lfloor x/y \right\rfloor, \ \text{if } y \neq 0$

$x \bmod 0 = x$

$y \neq 0$

$0 \le \frac{x}{y} - \left\lfloor \frac{x}{y} \right\rfloor = \frac{ x \bmod y} {y} < 1$

$y > 0$

$0 \le x \bmod y < y$

$y < 0$

$0 \ge x \bmod y >y$

$x - (x \bmod y)$

$y$

$x \bmod y$

$x$

$y$

$\left\lfloor x/y \right\rfloor$

$x$

$y$

$\text{mod}$

$5 \bmod 3 = 2$

$18 \bmod 3 = 0$

$-2 \bmod 3 = 1$

$x \bmod y = 0$

$x$

$y$

$x$

$y$

$y \backslash x$

$y$

$x$

$y$

$x \bmod y = 0$

$\text{mod}$

$x$

$y$

$\tan x = \tan (x \bmod \pi)$

$x \bmod 1$

$x$

$x = \left\lfloor x \right\rfloor + (x \bmod 1)$

商經由下取整函數來定義，商總是向負無窮取整，即使商已經是負數：

$$q=\left\lfloor\frac{a}{n}\right\rfloor$$

餘數和除數符號一致：

$$r = a - n \left\lfloor\frac{a}{n}\right\rfloor$$

Raymond T. Boute使用的歐幾里得除法定義中

$D$

$d$

$d \neq 0$

$q, r$

$q \in \mathbb{Z}$

$D = d \cdot q + r$

$0 \le r < |d|$

$D \operatorname{div} d = q$

$D \bmod d = r$

$$\begin{align} D \operatorname{div}\, (-d) &= -(D \operatorname{div} d)\\ D \bmod \left(-d\right) &= D \bmod d\\ (-D) \operatorname{div} d &= -(D \operatorname{div} d) - I \cdot J\\ (-D) \bmod d &= -(D \bmod d) + d \cdot I \cdot J \end{align}$$

$J = \operatorname{sign} d$

$I$

$I = \text{if } D/d \in \mathbb{Z} \text{ then } 0 \text{ else } 1$

要求滿足$0 \le r < |n|$，在這種情況下：

$$q = \sgn(n) \left\lfloor\frac{a}{\left|n\right|}\right\rfloor = \begin{cases} \left\lfloor\frac{a}{n}\right\rfloor & \text{if } n > 0 \\ - \left\lfloor- \frac{a}{n}\right\rfloor & \text{if } n < 0 \\ \end{cases}$$

這裡的$\sgn$是符號函數，餘數總是非負數:

$$r = a - |n| \left\lfloor \frac{a}{\left|n\right|} \right\rfloor = \begin{cases} a - n \left\lfloor \frac{a}{n} \right\rfloor & \text{if } n > 0 \\ a + n \left\lfloor - \frac{a}{n} \right\rfloor & \text{if } n < 0 \\ \end{cases}$$

Common Lisp的`round`函數和IEEE 754-1985使用「修約除法」（rounded division），商經由修約函數$\operatorname{round}$（約半成偶）來定義為：

$$q = \operatorname{round}\left(\frac{a}{n}\right)$$

當商為偶數時，餘數範圍是$-\frac{n}{2} \le r \le \frac{n}{2}$；當商為奇數時，餘數範圍是$-\frac{n}{2} < r < \frac{n}{2}$：

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

Common Lisp的`ceiling`函數使用「上取整除法」（ceiling division），商經由上取整函數定義為：

$$q = \left\lceil\frac{a}{n}\right\rceil$$

餘數與除數有相反的符號：

$$r = a - n \left\lceil\frac{a}{n}\right\rceil$$

## 記號

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

在一些沒有mod函數的環境中或許可使用等價的：`a - (n * int(a/n))`。這裡的`int()`函數事實上等價於截斷函數。

## 性質及恆等式

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

- $$(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$$
- 除法定義：僅當式子右側有定義時，即 $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$.

## 程式語言實現

語言｜算符｜整數｜浮點數｜定義

ABAP｜MOD｜是｜是｜歐幾里得式

ActionScript｜是｜否｜截斷

Ada｜是｜否｜下取整

是｜否｜截斷

ALGOL 68｜,｜是｜否｜類似歐幾里得式

AMPL｜是｜否｜截斷

APL｜`|``α|ω`計算$\omega\bmod\alpha$，得出ω除以α的餘數。｜是｜是｜下取整

AppleScript｜是｜否｜截斷

AutoLISP｜(rem d n)｜是｜否｜截斷

AWK｜是｜否｜截斷

bash｜是｜否｜截斷

BASIC｜Mod｜是｜否｜實現各異

bc｜是｜否｜截斷

CC++｜,｜是｜否｜截斷

fmod (C)std::fmod (C++)｜否｜是｜截斷

remainder (C)std::remainder (C++)｜否｜是｜修約

C#｜是｜是｜截斷

Math.IEEERemainder｜否｜是｜修約

Clarion語言｜是｜否｜截斷

Clean｜是｜否｜截斷

Clojure｜是｜否｜下取整

是｜否｜截斷

COBOL｜FUNCTION MOD｜是｜否｜下取整

FUNCTION REM｜是｜是｜截斷

CoffeeScript｜是｜否｜截斷

是｜否｜下取整

ColdFusion｜, MOD｜是｜否｜截斷

Common Intermediate Language｜(有符號)｜是｜是｜截斷

rem.un (無符號)｜是｜否｜不適用

Common Lisp｜是｜是｜下取整

是｜是｜截斷

Crystal語言｜, modulo｜是｜是｜下取整

remainder｜是｜是｜截斷

D｜是｜是｜截斷

Dart｜是｜是｜歐幾里得式

remainder｜是｜是｜截斷

Eiffel｜是｜否｜截斷

Elixir｜rem/2｜是｜否｜截斷

Integer.mod/2｜是｜否｜下取整

Elm｜modBy｜是｜否｜下取整

remainderBy｜是｜否｜截斷

Erlang｜是｜否｜截斷

math:fmod/2｜否｜是｜截斷 (同於C)

Euphoria｜是｜否｜下取整

remainder｜是｜否｜截斷

F#｜是｜是｜截斷

Math.IEEERemainder｜否｜是｜修約

Factor｜是｜否｜截斷

FileMaker｜Mod｜是｜否｜下取整

Forth｜是｜否｜實現定義

fm/mod｜是｜否｜下取整

sm/rem｜是｜否｜截斷

Fortran｜是｜是｜截斷

modulo｜是｜是｜下取整

Frink語言｜是｜否｜下取整

Full BASIC｜MOD｜是｜是｜下取整

REMAINDER｜是｜是｜截斷

GLSL｜是｜否｜未定義

否｜是｜下取整

GameMaker Studio (GML)｜,｜是｜否｜截斷

GDScript (Godot)｜是｜否｜截斷

fmod｜否｜是｜截斷

posmod｜是｜否｜歐幾里得式

fposmod｜否｜是｜歐幾里得式

Go｜是｜否｜截斷

math.Mod｜否｜是｜截斷

big.Int.Mod｜是｜否｜歐幾里得式

big.Int.Rem｜是｜否｜截斷

Groovy｜是｜否｜截斷

Haskell｜是｜否｜下取整

是｜否｜截斷

Data.Fixed.mod' (GHC)｜否｜是｜下取整

Haxe｜是｜否｜截斷

HLSL｜是｜是｜未定義

J｜`|`｜是｜否｜下取整

Java｜是｜是｜截斷

Math.floorMod｜是｜否｜下取整

JavaScriptTypeScript｜是｜是｜截斷

Julia｜是｜是｜下取整

,｜是｜是｜截斷

Kotlin｜,｜是｜是｜截斷

是｜是｜下取整

ksh｜是｜否｜截斷 (同於POSIX sh)

fmod｜否｜是｜截斷

LabVIEW｜是｜是｜截斷

LibreOffice｜=MOD｜是｜否｜下取整

Logo｜MODULO｜是｜否｜下取整

REMAINDER｜是｜否｜截斷

Lua 5｜是｜是｜下取整

Lua 4｜mod(x,y)｜是｜是｜截斷

Liberty BASIC｜MOD｜是｜否｜截斷

Mathcad｜mod(x,y)｜是｜否｜下取整

Maple｜e mod m (默認), modp(e, m)｜是｜否｜歐幾里得式

mods(e, m)｜是｜否｜修約

frem(e, m)｜是｜是｜修約

Mathematica｜Moda, b｜是｜否｜下取整

MATLAB｜是｜否｜下取整

是｜否｜截斷

Maxima｜是｜否｜下取整

remainder｜是｜否｜截斷

Maya嵌入語言｜是｜否｜截斷

Microsoft Excel｜=MOD｜是｜是｜下取整

Minitab｜MOD｜是｜否｜下取整

Modula-2｜MOD｜是｜否｜下取整

REM｜是｜否｜截斷

MUMPS｜是｜否｜下取整

Netwide Assembler (NASM, NASMX)｜, (無符號)｜是｜否｜不適用

(有符號)｜是｜否｜實現定義

Nim｜是｜否｜截斷

Oberon｜MOD｜是｜否｜類似下取整

Objective-C｜是｜否｜截斷 (同於C99)

Object Pascal, Delphi｜是｜否｜截斷

OCaml｜是｜否｜截斷

mod_float｜否｜是｜截斷

Occam｜是｜否｜截斷

Pascal (ISO-7185和ISO-10206)｜是｜否｜類似歐幾里得式

Perl｜是｜否｜下取整

POSIX::fmod｜否｜是｜截斷

PHP｜是｜否｜截斷

fmod｜否｜是｜截斷

PIC BASIC Pro｜是｜否｜截斷

PL/I｜是｜否｜下取整 (ANSI PL/I)

PowerShell｜是｜否｜截斷

Programming Code (PRC (Palm OS))｜MATH.OP - 'MOD; (\)'｜是｜否｜未定義

OpenEdge高級商務語言｜modulo｜是｜否｜截斷

Prolog (ISO 1995)｜是｜否｜下取整

是｜否｜截斷

PureBasic｜, Mod(x,y)｜是｜否｜截斷

PureScript｜`mod`｜是｜否｜歐幾里得式

Pure Data｜是｜否｜截斷 (同於C)

是｜否｜下取整

Python｜是｜是｜下取整

math.fmod｜否｜是｜截斷

math.remainder｜否｜是｜修約

Q#｜是｜否｜截斷

R｜是｜是｜下取整

Racket｜modulo｜是｜否｜下取整

remainder｜是｜否｜截斷

Raku｜否｜是｜下取整

RealBasic｜MOD｜是｜否｜截斷

Reason｜是｜否｜截斷

Rexx｜是｜是｜截斷

IBM RPG｜%REM｜是｜否｜截斷

Ruby｜, modulo｜是｜是｜下取整

remainder｜是｜是｜截斷

Rust｜是｜是｜截斷

rem_euclid｜是｜是｜歐幾里得式

SAS｜MOD｜是｜否｜截斷

Scala｜是｜是｜截斷

Scheme｜modulo｜是｜否｜下取整

remainder｜是｜否｜截斷

Scheme R6RS｜是｜否｜歐幾里得式

mod0｜是｜否｜修約

flmod｜否｜是｜歐幾里得式

flmod0｜否｜是｜修約

Scratch｜是｜是｜下取整

Seed7｜是｜是｜下取整

是｜是｜截斷

SenseTalk｜modulo｜是｜否｜下取整

是｜否｜截斷

Unix shell (包括bash、ash等。)｜是｜否｜截斷 (同於C)

Smalltalk｜是｜否｜下取整

rem:｜是｜否｜截斷

Snap!｜是｜否｜下取整

Parallax Propeller｜是｜否｜下取整

Solidity｜是｜否｜下取整

SQL (SQL:1999)｜mod(x,y)｜是｜否｜截斷

SQL (SQL:2011)｜是｜否｜截斷

Standard ML｜是｜否｜下取整

Int.rem｜是｜否｜截斷

Real.rem｜否｜是｜截斷

Stata｜mod(x,y)｜是｜否｜歐幾里得式

Swift｜是｜否｜截斷

remainder(dividingBy:)｜否｜是｜修約

truncatingRemainder(dividingBy:)｜否｜是｜截斷

Tcl｜是｜否｜下取整

fmod｜否｜是｜截斷 (同於C)

tcsh｜是｜否｜截斷

Torque (遊戲引擎)｜是｜否｜截斷

Turing語言｜是｜否｜下取整

Verilog (2001)｜是｜否｜截斷

VHDL｜是｜否｜下取整

是｜否｜截斷

VimL｜是｜否｜截斷

Visual Basic｜Mod｜是｜否｜截斷

WebAssembly｜i32.rem_u, i64.rem_u (無符號)｜是｜否｜不適用

i32.rem_s, i64.rem_s (有符號)｜是｜否｜截斷

x86彙編語言｜DIV(無符號)｜是｜否｜不適用

IDIV(有符號)｜是｜否｜截斷

XBase++｜是｜是｜截斷

Mod｜是｜是｜下取整

Zig｜, @mod, @rem｜是｜是｜截斷

Z3定理證明器｜,｜是｜否｜歐幾里得式

此外，很多電腦系統提供divmod功能，它同時產生商和餘數。例子x86架構的IDIV指令，C程式語言的div函數，和Python的divmod函數。

## 常見錯誤

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

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

```c++
bool is_odd(int n) {
    return n % 2 == 1;
}
```

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

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

```c++
bool is_odd(int n) {
    return n % 2 != 0;
}
```

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

```c++
bool is_odd(int n) {
    return n % 2 == 1 || n % 2 == -1;
}
```

## 性能問題

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

例如：2 的 n 次冪的模，可以通過逐位與運算實現：

`x % 2<sup>n</sup> == x & (2<sup>n</sup> - 1)`

例子，假定 x 為正數：

`x % 2 == x & 1`

`x % 4 == x & 3`

`x % 8 == x & 7`

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

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

## 用途

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

## 參見

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