模除

商数 ( $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)`^[1]	被除数 ^{[注 1]}
AWK	`%`	被除数
BASIC	`Mod`	未定义
C (ISO 1999)	`%`, `div`	被除数^[2]
C++ (ISO 2011)	`%`, `div`	被除数
C#	`%`	被除数
Clojure	`mod`	除数
Clojure	`rem`	被除数
CoffeeScript	`%`	被除数
CoffeeScript	`%%`	除数^[3]
Dart	`%`	非负
Dart	remainder()	被除数
Erlang	`rem`	被除数
F#	`%`	被除数
Fortran	`mod`	被除数
Fortran	`modulo`	除数
Go	`%`	被除数
Haskell	`mod`	除数
Haskell	`rem`	被除数
Kotlin	`%`	被除数
Java	`%`	被除数
Java	`Math.floorMod`	除数
JavaScript	`%`	被除数
Lua 5	`%`	除数
Mathematica	`Mod[a, b]`	除数
MATLAB	`mod`	除数
MATLAB	`rem`	被除数
Pascal (ISO-7185 and -10206)	`mod`	非负
Perl	`%`	除数
PHP	`%`	被除数
Prolog (ISO 1995^[4])	`mod`	除数
Prolog (ISO 1995^[4])	`rem`	被除数
Python	`%`	除数
Python	`math.fmod`	被除数
Racket	`remainder`	被除数
R语言	`%%`	除数
Ruby	`%, modulo()`	除数
Ruby	`remainder()`	被除数
Rust	`%`	被除数
Scala	`%`	被除数
Scheme R⁶RS^[5]	`mod`	非负
Scheme R⁶RS^[5]	`mod0`	最靠近0的数^[5]
SQL (SQL:2012)	`%`	被除数
Swift	`%`	被除数
Verilog (2001)	`%`	被除数
VHDL	`mod`	除数
VHDL	`rem`	被除数
Visual Basic	`Mod`	被除数
WebAssembly	`i32.rem_s, i64.rem_s`	被除数
x86 汇编	`IDIV`	被除数

不同编程语言下浮点数取模运算的符号
编程语言	操作符	结果与...同符号
C (ISO 1999)	`fmod`	被除数
C (ISO 1999)	`remainder`	最靠近0的数
C++ (ISO 2011)	`std::fmod`	被除数
C++ (ISO 2011)	`std::remainder`	最靠近0的数
C#	`%`	被除数
Common Lisp	`mod`	除数
Common Lisp	`rem`	被除数
Dart	`%`	非负
Dart	remainder()	被除数
F#	`%`	被除数
Fortran	`mod`	被除数
Fortran	`modulo`	除数
Go	`math.Mod`	被除数
Haskell (GHC)	`Data.Fixed.mod'`	除数
Java	`%`	被除数
JavaScript	`%`	被除数
Perl6	`%`	除数
PHP	`fmod`	被除数
Python	`%`	除数
Python	`math.fmod`	被除数
Ruby	`%, modulo()`	除数
Ruby	`remainder()`	被除数
Scheme R⁶RS	`flmod`	非负
Scheme R⁶RS	`flmod0`	最靠近0的数
Swift	`truncatingRemainder(dividingBy:)`	被除数

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

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

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

( 1 )

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

很多取模的实现都使用了截断除法，此时商由截断函数定义定义 $q = trunc(.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num,.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0 0.1em}.mw-parser-output .sfrac .den{border-top:1px solid}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}a/n)$ ，因此由等式 1 有，余数和被除数符号一致。商向零取整：结果等于普通除法所得的小数靠近 0 方向的第一个整数。
$r = a - n \operatorname{trunc}\left(\frac{a}{n}\right)$
高德纳^[7]定义的取底除法的商由取底函数定义： $q = [a / n]$ 。因此由等式 1 有，余数和除数符号一致。因为使用了取底函数，商总是向下取整，即使商已经是负数。
$r = a - n \left[\frac{a}{n}\right]$
Raymond T. Boute^[8]使用的欧几里得定义中，余数总是非负的 $0 \leq 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 -1 mod n$ 表示模反元素。当且仅当 $b$ 与 $n$ 互质时，等式左侧有定义： $[(b -1 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 -1 mod n)] mod n$ ，其他情况为未定义的。
乘法逆元： $[(ab mod n)(b -1 mod n)] mod n = a mod n$ .

性能问题

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

x % 2ⁿ == x & (2ⁿ - 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 到 n-1 取模则可判断一个数是否为质数。
进制之间的转换。
用于求取最大公约数的辗转相除法使用取模运算。
密码学中的应用：从古老的凯撒密码到现代常用的RSA、椭圆曲线密码，它们的实现过程均使用了取模运算。

参见

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

脚注

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

参考文献

↑ AutoCAD 2018 帮助: rem (AutoLISP). Autodesk, Inc. [2018-07-12] （中文）.
↑ ISO/IEC JTC. The ISO C99 Standard (ISO/IEC 9899:TC3 Committee Draft) (pdf). open-std.org: 6.5.5: 94. 2007-09-07 [2018-07-12] （英语）. If the quotient a/b is representable, the expression (a/b)*b + a%b shall equal a.
↑ jashkenas. CoffeeScript Language Reference - Operators and Aliases. coffeescript.org. [2018-07-12] （英语）. % works just like in JavaScript, while %% provides “dividend dependent modulo”
↑ J.P.E. Hodgson. Prolog: The ISO directives, control constructs and builtins.. 1999-04-12 [2018-07-12] （英语）. 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.0 ^5.1 ROBERT BRUCE FINDLER, JACOB MATTHEWS. Revised6 Report on the Algorithmic Language Scheme. r6rs.org. 2007-09-26 [2018-07-12] （英语）.
↑ Jones, Derek M. The New C Standard: An Economic and Cultural Commentary (PDF). Addison-Wesley. 2003 [2018-07-11]. ISBN 9780201709179 （英语）.
↑ Knuth, Donald. E. The Art of Computer Programming. Addison-Wesley. 1972 （英语）.
↑ 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 （英语）.
↑ Horvath, Adam. Faster division and modulo operation - the power of two. July 5, 2012 （英语）.

[2] 在 Visual LISP IDE 里测试可知结果与被除数同符号。 (rem 13 3)=>1; (rem -13 3)=>-1; (rem 13 -3)=>1; (rem -13 -3)=>-1

[7] 从数学上讲，正和负只是满足不等式的无穷多个解中的两个

[1] AutoCAD 2018 帮助: rem (AutoLISP). Autodesk, Inc. [2018-07-12] （中文）.

[C99-3] ISO/IEC JTC. The ISO C99 Standard (ISO/IEC 9899:TC3 Committee Draft) (pdf). open-std.org: 6.5.5: 94. 2007-09-07 [2018-07-12] （英语）. If the quotient a/b is representable, the expression (a/b)*b + a%b shall equal a.

[CoffeeScript-4] shkenas. CoffeeScript Language Reference - Operators and Aliases. coffeescript.org. [2018-07-12] （英语）. % works just like in JavaScript, while %% provides “dividend dependent modulo”

[5] J.P.E. Hodgson. Prolog: The ISO directives, control constructs and builtins.. 1999-04-12 [2018-07-12] （英语）. 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.

[r6rs-6] 5.0 ^5.1 ROBERT BRUCE FINDLER, JACOB MATTHEWS. Revised6 Report on the Algorithmic Language Scheme. r6rs.org. 2007-09-26 [2018-07-12] （英语）.

[C-CPP-Std-8] Jones, Derek M. The New C Standard: An Economic and Cultural Commentary (PDF). Addison-Wesley. 2003 [2018-07-11]. ISBN 9780201709179 （英语）.

[9] Knuth, Donald. E. The Art of Computer Programming. Addison-Wesley. 1972 （英语）.

[10] 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 （英语）.

[11] Horvath, Adam. Faster division and modulo operation - the power of two. July 5, 2012 （英语）.

[1]

[注 1]

[2]

[3]

[4]

[5]

[注 2]

[6]

[7]

[8]

[9]