模除

此条目介绍的是计算除法余数的二元运算。关于有关概念在数论中的应用，请见“模算数”。关于其他应用，请见“模 (消歧义)”。

模除（英语：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 年卡尔·弗里德里希·高斯引入模算数时产生的。
• 模幂运算
• 同馀