模除

商數 (q) 和
餘數 (r) 作為被除數 (a) 的函數時的圖像。左側是除數為正的情況，右側除數為負。從上至下分別使用了：向零取整、向下取整和歐幾里德除法。

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

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

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

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

定義與餘數的計算

不同程式語言下整數取模運算的符號

程式語言	操作符	結果與...同符號
AutoLISP	(rem d n)	被除數
AWK	%	被除數
BASIC	Mod	未定義
C (ISO 1999)	%, div	被除數
C++ (ISO 2011)	%, div	被除數
C#	%	被除數
Clojure	mod	除數
	rem	被除數
CoffeeScript	%	被除數
	%%	除數
Dart	%	非負
	remainder()	被除數
Erlang	rem	被除數
F#	%	被除數
Fortran	mod	被除數
	modulo	除數
Go	%	被除數
Haskell	mod	除數
	rem	被除數
Kotlin	%	被除數
Java	%	被除數
	Math.floorMod	除數
JavaScript	%	被除數
Lua 5	%	除數
Mathematica	Mod[a, b]	除數
MATLAB	mod	除數
	rem	被除數
Pascal (ISO-7185 and -10206)	mod	非負
Perl	%	除數
PHP	%	被除數
Prolog (ISO 1995)	mod	除數
	rem	被除數
Python	%	除數
	math.fmod	被除數
Racket	remainder	被除數
R語言	%%	除數
Ruby	%, modulo()	除數
	remainder()	被除數
Rust	%	被除數
Scala	%	被除數
Scheme R6RS	mod	非負
	mod0	最靠近0的數
SQL (SQL:2012)	%	被除數
Swift	%	被除數
Verilog (2001)	%	被除數
VHDL	mod	除數
	rem	被除數
Visual Basic	Mod	被除數
WebAssembly	i32.rem_s, i64.rem_s	被除數
x86 彙編	IDIV	被除數

不同程式語言下浮點數取模運算的符號

程式語言	操作符	結果與...同符號
C (ISO 1999)	fmod	被除數
	remainder	最靠近0的數
C++ (ISO 2011)	std::fmod	被除數
	std::remainder	最靠近0的數
C#	%	被除數
Common Lisp	mod	除數
	rem	被除數
Dart	%	非負
	remainder()	被除數
F#	%	被除數
Fortran	mod	被除數
	modulo	除數
Go	math.Mod	被除數
Haskell (GHC)	Data.Fixed.mod'	除數
Java	%	被除數
JavaScript	%	被除數
Perl6	%	除數
PHP	fmod	被除數
Python	%	除數
	math.fmod	被除數
Ruby	%, modulo()	除數
	remainder()	被除數
Scheme R6RS	flmod	非負
	flmod0	最靠近0的數
Swift	truncatingRemainder(dividingBy:)	被除數

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

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

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

( 1 )

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

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

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

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

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

• Raymond T. Boute使用的歐幾里得定義中，餘數總是非負的 0 ≤ r，這與歐幾里得算法是一致的。 在這種情況下：

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

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

  或者等價的：

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

  這裡的 sgn 是符號函數，因此

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

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

常見錯誤

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

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

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

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

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

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

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

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

記號

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

a % n

或

a mod n

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

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

等價性

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

• 恆等式：
  • (a mod n) mod n = a mod n
  • 對所有的正數 x 有：n^x mod n = 0
  • 如果 p 是一個質數，且不為 b 的因數，此時由費馬小定理有：ab^p−1 mod p = a mod p
• 逆運算：
  • [(−a mod n) + (a mod n)] mod n = 0.
  • b⁻¹ mod n 表示模反元素。若且唯若 b 與 n 互質時，等式左側有定義：[(b⁻¹ mod n)(b mod n)] mod n = 1。
• 分配律：
  • (a + b) mod n = [(a mod n) + (b mod n)] mod n
  • ab mod n = [(a mod n)(b mod n)] mod n
  • d mod (abc) = (d mod a) + a[(d \ a) mod b] + ab[(d \ a \ b) mod c]，符號 \ 是歐幾里德除法中的除法操作符，運算結果為商
  • c mod (a+b) = (c mod a) + [bc \ (a+b)] mod b - [bc \ (a + b)] mod a.
• 除法定義：僅當式子右側有定義時，即 b、n 互質時有：a/b mod n = [(a mod n)(b⁻¹ mod n)] mod n，其他情況為未定義的。
• 乘法逆元：[(ab mod n)(b⁻¹ mod n)] mod n = a mod 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 年卡爾·弗里德里希·高斯引入模算數時產生的。
• 模冪運算
• 同餘