模除

此條目介紹的是計算除法餘數的二元運算。關於有關概念在數論中的應用，請見「模算數」。關於其他應用，請見「模 (消歧義)」。

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

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

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

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

各種定義

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

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

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

1

即使如此，當餘數非${\displaystyle 0}$時，餘數的符號仍然是有歧義的：餘數非${\displaystyle 0}$時，它的符號有兩種選擇，一個是正號而另一個是負號^[a]。通常情況下，在數論中總是選擇正餘數。但在編程中，選擇餘數的符號依賴於程式語言和被除數${\displaystyle a}$或除數${\displaystyle n}$的符號。在程式語言所定義的整數模除中，ISO/IEC標準Pascal^[1]和ALGOL 68^[2]，在計算出的餘數r為負數時，返回正數${\displaystyle r+|n|}$作為結果^[b]；另一些程式語言如ISO/IEC C90，當被除數${\displaystyle a}$或除數${\displaystyle n}$是負數時，C90標準並沒有做具體的規定，而是留給編譯器去定義並實現^[3]。在大多數系統中${\displaystyle a{\bmod {0}}}$是未定義的，雖然有些系統定義它就等於${\displaystyle a}$。更多詳情參見後續章節表格。

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

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

  餘數和被除數符號一致：

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

• 高德納定義的「下取整除法」（英語：floored division）^[4]，商經由下取整函數來定義，商總是向負無窮取整，即使商已經是負數：
  ${\displaystyle q=\left\lfloor {\frac {a}{n}}\right\rfloor }$

  餘數和除數符號一致：

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

• Raymond T. Boute使用的歐幾里得除法定義中^[5]，要求滿足${\displaystyle 0\leq r<|n|}$，在這種情況下：
  ${\displaystyle q=\operatorname {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}}}$

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

  ${\displaystyle 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（英語：IEEE 754-1985）使用「修約除法」（英語：rounded division），商經由修約函數${\displaystyle \operatorname {round} }$（約半成偶）來定義為：
  ${\displaystyle q=\operatorname {round} \left({\frac {a}{n}}\right)}$

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

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

• Common Lisp的ceiling函數使用「上取整除法」（英語：ceiling division），商經由上取整函數定義為：
  ${\displaystyle q=\left\lceil {\frac {a}{n}}\right\rceil }$

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

  ${\displaystyle 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()函數事實上等價於截斷函數。

性質及恆等式

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

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

程式語言實現

在各種程式語言中的模除運算

語言	算符	整數	浮點數	定義
ABAP	MOD	是	是	歐幾里得式
ActionScript	%	是	否	截斷
Ada	mod	是	否	下取整[6]
	rem	是	否	截斷[6]
ALGOL 68	÷×, mod	是	否	類似歐幾里得式[c]
AMPL	mod	是	否	截斷
APL	|[d]	是	是	下取整
AppleScript	mod	是	否	截斷
AutoLISP	(rem d n)	是	否	截斷
AWK	%	是	否	截斷
bash	%	是	否	截斷
BASIC	Mod	是	否	實現各異
bc	%	是	否	截斷
C C++	%, div	是	否	截斷[e]
	fmod (C) std::fmod (C++)	否	是	截斷[9]
	remainder (C) std::remainder (C++)	否	是	修約
C#	%	是	是	截斷
	Math.IEEERemainder	否	是	修約[10]
Clarion（英語：Clarion (programming language)）	%	是	否	截斷
Clean	rem	是	否	截斷
Clojure	mod	是	否	下取整[11]
	rem	是	否	截斷[12]
COBOL	FUNCTION MOD	是	否	下取整[13]
	FUNCTION REM	是	是	截斷[13]
CoffeeScript	%	是	否	截斷
	%%	是	否	下取整[14]
ColdFusion	%, MOD	是	否	截斷
Common Intermediate Language	rem (有符號)	是	是	截斷[15]
	rem.un (無符號)	是	否	不適用
Common Lisp	mod	是	是	下取整
	rem	是	是	截斷
Crystal（英語：Crystal (programming language)）	%, modulo	是	是	下取整
	remainder	是	是	截斷
D	%	是	是	截斷[16]
Dart	%	是	是	歐幾里得式[17]
	remainder()	是	是	截斷[18]
Eiffel	\\	是	否	截斷
Elixir	rem/2	是	否	截斷[19]
	Integer.mod/2	是	否	下取整[20]
Elm	modBy	是	否	下取整[21]
	remainderBy	是	否	截斷[22]
Erlang	rem	是	否	截斷
	math:fmod/2	否	是	截斷 (同於C)[23]
Euphoria	mod	是	否	下取整
	remainder	是	否	截斷
F#	%	是	是	截斷
	Math.IEEERemainder	否	是	修約[10]
Factor	mod	是	否	截斷
FileMaker	Mod	是	否	下取整
Forth	mod	是	否	實現定義
	fm/mod	是	否	下取整
	sm/rem	是	否	截斷
Fortran	mod	是	是	截斷
	modulo	是	是	下取整
Frink（英語：Frink (programming language)）	mod	是	否	下取整
Full BASIC（英語：Full BASIC）	MOD	是	是	下取整[24]
	REMAINDER	是	是	截斷[25]
GLSL	%	是	否	未定義[26]
	mod	否	是	下取整[27]
GameMaker Studio (GML)	mod, %	是	否	截斷
GDScript (Godot)	%	是	否	截斷
	fmod	否	是	截斷
	posmod	是	否	歐幾里得式
	fposmod	否	是	歐幾里得式
Go	%	是	否	截斷[28]
	math.Mod	否	是	截斷[29]
	big.Int.Mod	是	否	歐幾里得式[30]
	big.Int.Rem	是	否	截斷[31]
Groovy	%	是	否	截斷
Haskell	mod	是	否	下取整[32]
	rem	是	否	截斷[32]
	Data.Fixed.mod' (GHC)	否	是	下取整
Haxe	%	是	否	截斷
HLSL	%	是	是	未定義[33]
J	|[d]	是	否	下取整
Java	%	是	是	截斷
	Math.floorMod	是	否	下取整
JavaScript TypeScript	%	是	是	截斷
Julia	mod	是	是	下取整[34]
	%, rem	是	是	截斷[35]
Kotlin	%, rem	是	是	截斷[36]
	mod	是	是	下取整[37]
ksh	%	是	否	截斷 (同於POSIX sh)
	fmod	否	是	截斷
LabVIEW	mod	是	是	截斷
LibreOffice	=MOD()	是	否	下取整
Logo	MODULO	是	否	下取整
	REMAINDER	是	否	截斷
Lua 5	%	是	是	下取整
Lua 4	mod(x,y)	是	是	截斷
Liberty BASIC（英語：Liberty BASIC）	MOD	是	否	截斷
Mathcad	mod(x,y)	是	否	下取整
Maple	e mod m (默認), modp(e, m)	是	否	歐幾里得式
	mods(e, m)	是	否	修約
	frem(e, m)	是	是	修約
Mathematica	Mod[a, b]	是	否	下取整
MATLAB	mod	是	否	下取整
	rem	是	否	截斷
Maxima	mod	是	否	下取整
	remainder	是	否	截斷
Maya Embedded Language（英語：Maya Embedded Language）	%	是	否	截斷
Microsoft Excel	=MOD()	是	是	下取整
Minitab	MOD	是	否	下取整
Modula-2	MOD	是	否	下取整
	REM	是	否	截斷
MUMPS（英語：MUMPS）	#	是	否	下取整
Netwide Assembler (NASM, NASMX)	%, div (無符號)	是	否	不適用
	%% (有符號)	是	否	實現定義[38]
Nim	mod	是	否	截斷
Oberon	MOD	是	否	類似下取整[f]
Objective-C	%	是	否	截斷 (同於C99)
Object Pascal, Delphi	mod	是	否	截斷
OCaml	mod	是	否	截斷[39]
	mod_float	否	是	截斷[40]
Occam	\	是	否	截斷
Pascal (ISO-7185和ISO-10206)	mod	是	否	類似歐幾里得式[c]
Perl	%	是	否	下取整[g]
	POSIX::fmod	否	是	截斷
PHP	%	是	否	截斷[42]
	fmod	否	是	截斷[43]
PIC BASIC Pro	\\	是	否	截斷
PL/I	mod	是	否	下取整 (ANSI PL/I)
PowerShell	%	是	否	截斷
Programming Code (PRC（英語：PRC (Palm OS)）)	MATH.OP - 'MOD; (\)'	是	否	未定義
Progress（英語：OpenEdge Advanced Business Language）	modulo	是	否	截斷
Prolog (ISO 1995[44])	mod	是	否	下取整
	rem	是	否	截斷
PureBasic	%, Mod(x,y)	是	否	截斷
PureScript	`mod`	是	否	歐幾里得式[45]
Pure Data	%	是	否	截斷 (同於C)
	mod	是	否	下取整
Python	%	是	是	下取整
	math.fmod	否	是	截斷
	math.remainder	否	是	修約
Q#	%	是	否	截斷[46]
R	%%	是	是	下取整[47]
Racket	modulo	是	否	下取整
	remainder	是	否	截斷
Raku	%	否	是	下取整
RealBasic（英語：RealBasic）	MOD	是	否	截斷
Reason	mod	是	否	截斷
Rexx	//	是	是	截斷
RPG（英語：IBM RPG）	%REM	是	否	截斷
Ruby	%, modulo()	是	是	下取整
	remainder()	是	是	截斷
Rust	%	是	是	截斷
	rem_euclid()	是	是	歐幾里得式[48]
SAS	MOD	是	否	截斷
Scala	%	是	是	截斷
Scheme	modulo	是	否	下取整
	remainder	是	否	截斷
Scheme R6RS	mod	是	否	歐幾里得式[49]
	mod0	是	否	修約[49]
	flmod	否	是	歐幾里得式
	flmod0	否	是	修約
Scratch	mod	是	是	下取整
Seed7（英語：Seed7）	mod	是	是	下取整
	rem	是	是	截斷
SenseTalk（英語：SenseTalk）	modulo	是	否	下取整
	rem	是	否	截斷
Unix shell (包括bash、ash等。)	%	是	否	截斷 (同於C)[50]
Smalltalk	\\	是	否	下取整
	rem:	是	否	截斷
Snap!	mod	是	否	下取整
Spin（英語：Parallax Propeller#Built in Spin byte code interpreter）	//	是	否	下取整
Solidity	%	是	否	下取整
SQL (SQL:1999（英語：SQL:1999）)	mod(x,y)	是	否	截斷
SQL (SQL:2011（英語：SQL:2011）)	%	是	否	截斷
Standard ML	mod	是	否	下取整
	Int.rem	是	否	截斷
	Real.rem	否	是	截斷
Stata	mod(x,y)	是	否	歐幾里得式
Swift	%	是	否	截斷[51]
	remainder(dividingBy:)	否	是	修約[52]
	truncatingRemainder(dividingBy:)	否	是	截斷[53]
Tcl	%	是	否	下取整
	fmod()	否	是	截斷 (同於C)
tcsh	%	是	否	截斷
Torque（英語：Torque (game engine)）	%	是	否	截斷
Turing（英語：Turing (programming language)）	mod	是	否	下取整
Verilog (2001)	%	是	否	截斷
VHDL	mod	是	否	下取整
	rem	是	否	截斷
VimL	%	是	否	截斷
Visual Basic	Mod	是	否	截斷
WebAssembly	i32.rem_u, i64.rem_u (無符號)	是	否	不適用
	i32.rem_s, i64.rem_s (有符號)	是	否	截斷[54]
x86 assembly（英語：x86 assembly language）	DIV(無符號)	是	否	不適用
	IDIV(有符號)	是	否	截斷
XBase++（英語：XBase++）	%	是	是	截斷
	Mod()	是	是	下取整
Zig	%, @mod, @rem	是	是	截斷[55]
Z3 theorem prover（英語：Z3 Theorem Prover）	div, mod	是	否	歐幾里得式

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

常見錯誤

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

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

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

但在一個取模結果與被除數符號相同的程式語言里，這樣做是錯的。因為當被除數 n 是奇數且為負數時， ${\displaystyle n{\bmod {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;
}

性能問題

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

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

例子，假定 x 為正數：

x % 2 == x & 1

x % 4 == x & 3

x % 8 == x & 7

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

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

用途

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

參見

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