模除

模除（又稱模数、取模操作、取模運算等，英語：modulo 有时也称作 modulus）得到的是一个数除以另一个数的余数。

  商數 (${\displaystyle q}$) 和   餘數 (${\displaystyle r}$) 作為被除數 (${\displaystyle a}$) 的函數時的圖像。左侧是除数为正的情况，右侧除数为负。从上至下分别使用了：向零取整、向下取整和欧几里德除法。

给定两个正整数：被除数 ${\displaystyle a}$ 和除数 ${\displaystyle n}$，a modulo n (缩写为 ${\displaystyle a{\bmod {n}}}$)得到的是使用欧几里德除法时 ${\displaystyle {\frac {a}{n}}}$ 的余数。 举个例子：计算表达式 "${\displaystyle 5{\bmod {2}}}$" 得到 1，因为 ${\displaystyle 5\div 2=2\ldots 1}$（5 除以 2 商 2 餘1）；而 "${\displaystyle 9{\bmod {3}}}$" 得到 0，因为 ${\displaystyle 9\div 3=3\ldots 0}$；注意：如果使用计算器做除法，不能整除时，你不会得到商，而是会得到一个小数，如：${\displaystyle 5\div 2=2.5}$。

虽然通常情况下 ${\displaystyle a}$ 和 ${\displaystyle n}$ 都是整数，但许多计算系统允许其他类型的数字操作，如：对浮点数取模。一个整数对 ${\displaystyle n}$ 取模的结果范围为： 0 到 ${\displaystyle n-1}$（${\displaystyle a{\bmod {1}}}$ 恒等于 0；${\displaystyle a{\bmod {0}}}$ 则是未定义的，在编程语言里可能会导致除零错误）。 有关概念在数论中的应用请参阅模算數。

当 ${\displaystyle a}$ 或 ${\displaystyle n}$ 为负数时，通常的定义就不适用了，不同的编程语言对结果有不同的处理。

定義与余数的计算

不同程式語言下整数取模运算的符号

程式語言	操作符	结果与...同符号
AutoLISP	(rem d n)^[1]	被除数 ^[註 1]
AWK	%	被除数
BASIC	Mod	未定义
C (ISO 1999)	%, div	被除数^[2]
C++ (ISO 2011)	%, div	被除数
C#	%	被除数
Clojure	mod	除数
	rem	被除数
CoffeeScript	%	被除数
	%%	除数^[3]
Dart	%	非负
	remainder()	被除数
Erlang	rem	被除数
F#	%	被除数
Fortran	mod	被除数
	modulo	除数
Go	%	被除数
Haskell	mod	除数
	rem	被除数
Julia	%, 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^[4])	mod	除数
	rem	被除数
Python	%	除数
	math.fmod	被除数
Racket	remainder	被除数
R语言	%%	除数
Ruby	%, modulo()	除数
	remainder()	被除数
Rust	%	被除数
Scala	%	被除数
Scheme R^6RS^[5]	mod	非负
	mod0	最靠近0的数^[5]
SQL (SQL:2012)	%	被除数
Swift	%	被除数
Verilog (2001)	%	被除数
VHDL	mod	除数
	rem	被除数
Visual Basic	Mod	被除数
WebAssembly	i32.rem_s, i64.rem_s	被除数
x86 汇编（英语：x86 assembly language）	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 R^6RS	flmod	非负
	flmod0	最靠近0的数
Swift	truncatingRemainder(dividingBy:)	被除数

在数学中，取模运算的结果就是欧几里德除法的余数。当然也有许多其他的定义方式。计算机和计算器有许多种表示和储存数字的方法，因此在不同的硬件环境下、不同的编程语言中，取模运算有着不同的定义。

几乎所有的计算系统中，${\displaystyle a}$  除 ${\displaystyle n}$  得到商 ${\displaystyle q}$  和余数 ${\displaystyle r}$  均满足以下式子：

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

( 1 )

然而这样做，当余数非 0 时，余数的符号仍然是有歧义的：余数非 0 时，它的符号有两种选择，一个正、一个负。^{[註 2]} 通常情况下，在数论中总是使用正余数。但在编程语言中，余数的符号取决于编程语言的类型和被除数 a 或除数 ${\displaystyle n}$  的符号。 标准 Pascal 和 ALGOL 68 总是使用 0 或正余数；另一些编程语言，如 C90 ，当被除数 ${\displaystyle a}$  和除数 ${\displaystyle n}$  都是负数时，C90 标准并没有做具体的规定，而是留给编译器去定义并实现^[6]。 在大多数系统上 ${\displaystyle a{\bmod {0}}}$  时未定义的，虽然有些系统定义它就等于 ${\displaystyle a}$ 。更多详情参见表格。

• 很多取模的实现都使用了截断除法，此时商由截断函数定义定义 ${\displaystyle q=\mathrm {trunc} \left({\frac {a}{n}}\right)}$ ，因此由等式 1 有，余数和被除数符号一致。商向零取整：结果等于普通除法所得的小数靠近 0 方向的第一个整数。

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

• 高德纳^[7]定义的取底除法的商由取底函数定义：${\displaystyle q=[{\frac {a}{n}}]}$ 。因此由等式 1 有，余数和除数符号一致。因为使用了取底函数，商总是向下取整，即使商已经是负数。

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

• Raymond T. Boute^[8]使用的欧几里得定义中，余数总是非负的 ${\displaystyle 0\leq r}$ ，这与欧几里得算法是一致的。

在这种情况下：

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

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

或者等价的：

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

这里的 ${\displaystyle \mathrm {sgn} }$  是符号函数，因此

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

• Common Lisp 也定义了自己的舍入除法和进位除法，商分别定义为 ${\displaystyle q=\mathrm {round} \left({\frac {a}{n}}\right)}$  和 ${\displaystyle q=-\left[{\frac {-a}{n}}\right]}$ 。
• IEEE 754（英语：IEEE 754-1985） 定义了一个取余函数，商被定义为 ${\displaystyle {\frac {a}{n}}}$ ，依据舍入约定（英语：IEEE 754-1985#Rounding floating-point numbers）取整。因此余数的符号选定为最接近0。

常见错误

当取模的结果与被除数符号相同时，可能会导致意想不到的错误。

举个例子：如果需要判断一个整数是否为奇数，有人可能会测试这个数除 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; } 

记号

一些计算器有取模 mod() 按钮，很多编程语言里也有类似的函数，通常像 mod(a, n) 这样。 有些语言也支持在表达式内使用 "%"、"mod" 或 "Mod" 作为取模或取余操作符。

a % n

或

a mod n

或者在一些没有 mod() 函数的环境中使用等价的： （注意 'int' 事实上等价于截断函数${\displaystyle {\frac {a}{n}}}$ ，进行了向 0 取整）

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

等价性

一些取模操作，经过分解和展开可以等同于其他数学运算。这在密码学的证明中十分有用，例如：迪菲-赫爾曼密鑰交換。

• 恒等式：
  • ${\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 d{\bmod {(}}abc)=(d{\bmod {a}})+a[(d\backslash a{\bmod {b}})]+ab[(d\backslash a\backslash b){\bmod {c}}]}$ ，符号 \ 是欧几里德除法中的除法操作符，运算结果为商
  • ${\displaystyle c{\bmod {(}}a+b)=(c{\bmod {a}})+[bc\backslash (a+b)]{\bmod {b}}-[bc\backslash (a+b)]{\bmod {a}}}$ .
• 除法定义：仅当式子右侧有定义时，即 ${\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}}}$ .

性能问题

可以通过依次计算带余数的除法实现取模操作。特殊情况下，如某些硬件上，存在更快的实现。 例如：2 的 n 次幂的模，可以通过逐位与运算实现：

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

例子，假定 x 为正数：

x % 2 == x & 1

x % 4 == x & 3

x % 8 == x & 7

在进行位操作比取模操作效率更高的设备或软件环境中，以上形式的取模运算速度更快。^[9]

编译器可以自动识别出对 2 的 n 次幂取模的表达式，自动将其优化为 expression & (constant-1)。这样可以在兼顾效率的情况下写出更整洁的代码。这个优化在取模结果与被除数符号一致的语言中（包括 C 语言）不能使用，除非被除数是无符号整数。这是因为如果被除数是负数，则结果也是负数，但 expression & (constant-1) 总是正数，进行这样的优化就会导致错误，无符号整数则没有这个问题。

用途

• 取模运算可用于判断一个数是否能被另一个数整除。对 2 取模即可判断整数的奇偶性；从 2 到 ${\displaystyle n-1}$  取模则可判断一个数是否为质数。
• 進制之間的轉換。
• 用于求取最大公约数的輾轉相除法使用取模运算。
• 密码学中的应用：从古老的凯撒密码到现代常用的RSA、椭圆曲线密码，它们的实现过程均使用了取模运算。

參見

• 模 (消歧义)和模 (术语)（英语：modulo (jargon)） —— “模数（Modulo）”这个词的许多用法，都是 1801 年卡爾·弗里德里希·高斯引入模算數时产生的。
• 模幂运算
• 同餘

脚注

1. 在 Visual LISP IDE 里测试可知结果与被除数同符号。 (rem 13 3)=>1; (rem -13 3)=>-1; (rem 13 -3)=>1; (rem -13 -3)=>-1
2. 从数学上讲，正和负只是满足不等式的无穷多个解中的两个

参考文献

1. AutoCAD 2018 帮助: rem (AutoLISP). Autodesk, Inc. [2018-07-12] （中文）. 
2. ISO/IEC JTC. (PDF). open-std.org: 6.5.5: 94. 2007-09-07 [2018-07-12]. （原始内容 (pdf)存档于2018-06-24） （英语）. If the quotient a/b is representable, the expression (a/b)*b + a%b shall equal a. 
3. jashkenas. . coffeescript.org. [2018-07-12]. （原始内容存档于2018-07-11） （英语）. % works just like in JavaScript, while %% provides “dividend dependent modulo” 
4. J.P.E. Hodgson. . 1999-04-12 [2018-07-12]. （原始内容存档于2017-12-25） （英语）. A conforming processor is required to support the arithmetic operations specified by the following tables. They conform to the ISO/IEC 10967-1 Language Independent Arithmetic standard. 
5. ROBERT BRUCE FINDLER, JACOB MATTHEWS. . r6rs.org. 2007-09-26 [2018-07-12]. （原始内容存档于2018-03-15） （英语）. 
6. Jones, Derek M. (PDF). Addison-Wesley. 2003 [2018-07-11]. ISBN 9780201709179. （原始内容 (PDF)存档于2018-07-11） （英语）. 
7. Knuth, Donald. E. The Art of Computer Programming. Addison-Wesley. 1972 （英语）. 
8. Boute, Raymond T. The Euclidean definition of the functions div and mod. ACM Transactions on Programming Languages and Systems (ACM Press (New York, NY, USA)). April 1992, 14 (2): 127–144. doi:10.1145/128861.128862 （英语）. 
9. Horvath, Adam. . July 5, 2012. （原始内容存档于2018-03-05） （英语）.