模除

<image>

模除（modulo），又称模算术、取模、取模运算等，它得出一个数除以另一个数的余数。给定两个正数：被除数 $a$ 和除数 $n$ (有时也称作模数，英文写作modulus)，$a \,\operatorname{modulo}\, n$（通常缩写为$a \bmod n$），得到的是使用欧几里得除法时的余数。$a \bmod 1$所得之数被称为$a$的小数部分。

举个例子：计算表达式$5\bmod 2$得到$1$，因为$5\div 2$的商为$2$而余数为$1$；而$9\bmod 3$得到$0$，因为$9\div 3$的商为$3$而余数为$0$；做除法不能整除时得到是有理数，平常使用的计算器采用了有限个数位的十进制表示法，它以小数点分隔整数部分和小数部分，比如$5\div 2=2.5$。

虽然通常情况下模除的被除数$a$和除数$n$都是整数，但许多计算系统允许其他类型的数值运算，比如对浮点数取模。在所有计算系统中当被除数$a$和除数$n$都是正数时，结果的余数$r$的范围为$0 \le r < n$；而$a \bmod 0$经常是未定义的，在编程语言里可能会导致除以零错误。当被除数$a$或除数$n$为负数时，不同的编程语言对结果有不同的处理。

## 各种定义

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

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

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

即使如此，当余数非$0$时，余数的符号仍然是有歧义的：余数非$0$时，它的符号有两种选择，一个是正号而另一个是负号。通常情况下，在数论中总是选择正余数。但在编程中，选择余数的符号依赖于编程语言和被除数$a$或除数$n$的符号。在编程语言所定义的整数模除中，ISO/IEC标准Pascal和ALGOL 68，在计算出的余数`r`为负数时，返回正数$r + |n|$作为结果；另一些编程语言如ISO/IEC C90，当被除数$a$或除数$n$是负数时，C90标准并没有做具体的规定，而是留给编译器去定义并实现

```c
#include <stdio.h>

int main(void)
{
int x = -1,
y = +3;
if ((x%y > 0) ||
    ((x+y)%y == x%y))
    printf("This is a C90 translator behaving differently than C99\n");
}
```

在大多数系统中$a \bmod 0$是未定义的，虽然有些系统定义它就等于$a$。更多详情参见后续章节表格。

很多取模的实现都使用了“截断除法”（truncated division），商经由截尾函数来定义，商向零取整，结果等于普通除法所得的小数靠近$0$方向的第一个整数：

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

余数和被除数符号一致：

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

高德纳定义的“下取整除法”（floored division）

$x$

$\left\lfloor x \right\rfloor$

$x$

$x$

$\left\lceil x \right\rceil$

$x$

$x$

$\left\lceil x \right\rceil = \left\lfloor x \right\rfloor$

$x$

$\left\lceil x \right\rceil = \left\lfloor x \right\rfloor + 1$

$x$

$\left\lfloor -x \right\rfloor = -\left\lceil x \right\rceil$

$x - 1 < \left\lfloor x \right\rfloor \le x \le \left\lceil x \right\rceil < x + 1$

$x$

$y$

$x \bmod y = x - y \left\lfloor x/y \right\rfloor, \ \text{if } y \neq 0$

$x \bmod 0 = x$

$y \neq 0$

$0 \le \frac{x}{y} - \left\lfloor \frac{x}{y} \right\rfloor = \frac{ x \bmod y} {y} < 1$

$y > 0$

$0 \le x \bmod y < y$

$y < 0$

$0 \ge x \bmod y >y$

$x - (x \bmod y)$

$y$

$x \bmod y$

$x$

$y$

$\left\lfloor x/y \right\rfloor$

$x$

$y$

$\text{mod}$

$5 \bmod 3 = 2$

$18 \bmod 3 = 0$

$-2 \bmod 3 = 1$

$x \bmod y = 0$

$x$

$y$

$x$

$y$

$y \backslash x$

$y$

$x$

$y$

$x \bmod y = 0$

$\text{mod}$

$x$

$y$

$\tan x = \tan (x \bmod \pi)$

$x \bmod 1$

$x$

$x = \left\lfloor x \right\rfloor + (x \bmod 1)$

商经由下取整函数来定义，商总是向负无穷取整，即使商已经是负数：

$$q=\left\lfloor\frac{a}{n}\right\rfloor$$

余数和除数符号一致：

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

Raymond T. Boute使用的欧几里得除法定义中

$D$

$d$

$d \neq 0$

$q, r$

$q \in \mathbb{Z}$

$D = d \cdot q + r$

$0 \le r < |d|$

$D \operatorname{div} d = q$

$D \bmod d = r$

$$\begin{align} D \operatorname{div}\, (-d) &= -(D \operatorname{div} d)\\ D \bmod \left(-d\right) &= D \bmod d\\ (-D) \operatorname{div} d &= -(D \operatorname{div} d) - I \cdot J\\ (-D) \bmod d &= -(D \bmod d) + d \cdot I \cdot J \end{align}$$

$J = \operatorname{sign} d$

$I$

$I = \text{if } D/d \in \mathbb{Z} \text{ then } 0 \text{ else } 1$

要求满足$0 \le r < |n|$，在这种情况下：

$$q = \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}$$

这里的$\sgn$是符号函数，余数总是非负数:

$$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-1985使用“修约除法”（rounded division），商经由修约函数$\operatorname{round}$（约半成偶）来定义为：

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

当商为偶数时，余数范围是$-\frac{n}{2} \le r \le \frac{n}{2}$；当商为奇数时，余数范围是$-\frac{n}{2} < r < \frac{n}{2}$：

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

Common Lisp的`ceiling`函数使用“上取整除法”（ceiling division），商经由上取整函数定义为：

$$q = \left\lceil\frac{a}{n}\right\rceil$$

余数与除数有相反的符号：

$$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()`函数事实上等价于截断函数。

## 性质及恒等式

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

- $$(a \bmod n) \bmod n=a \bmod n$$
- 对所有的正整数 $x$ 有：$n^x \bmod n=0$
- 如果 $p$ 是一个质数，且不为 $b$ 的因数，此时由费马小定理有：$ab^{p-1} \bmod p=a \bmod p$
- $[(-a \bmod n)+(a \bmod n)]\bmod n=0$.
- $b^{-1} \bmod n$ 表示模反元素。当且仅当 $b$ 与 $n$ 互质时，等式左侧有定义：$[(b^{-1} \bmod n)(b \bmod n)] \bmod n =1$。
- $$(a+b) \bmod n=[(a \bmod n)+(b \bmod n)] \bmod n$$
- $$ab \bmod n=[(a \bmod n)(b \bmod n)] \bmod n$$
- 除法定义：仅当式子右侧有定义时，即 $b$、$n$ 互质时有：$\frac{a}{b} \bmod n=[(a \bmod n)(b^{-1} \bmod n)]\bmod n$，其他情况为未定义的。
- 乘法逆元：$[(ab \bmod n)(b^{-1} \bmod n)]\bmod n=a \bmod n$.

## 编程语言实现

语言｜算符｜整数｜浮点数｜定义

ABAP｜MOD｜是｜是｜欧几里得式

ActionScript｜是｜否｜截断

Ada｜是｜否｜下取整

是｜否｜截断

ALGOL 68｜,｜是｜否｜类似欧几里得式

AMPL｜是｜否｜截断

APL｜`|``α|ω`计算$\omega\bmod\alpha$，得出ω除以α的余数。｜是｜是｜下取整

AppleScript｜是｜否｜截断

AutoLISP｜(rem d n)｜是｜否｜截断

AWK｜是｜否｜截断

bash｜是｜否｜截断

BASIC｜Mod｜是｜否｜实现各异

bc｜是｜否｜截断

CC++｜,｜是｜否｜截断

fmod (C)std::fmod (C++)｜否｜是｜截断

remainder (C)std::remainder (C++)｜否｜是｜修约

C#｜是｜是｜截断

Math.IEEERemainder｜否｜是｜修约

Clarion语言｜是｜否｜截断

Clean｜是｜否｜截断

Clojure｜是｜否｜下取整

是｜否｜截断

COBOL｜FUNCTION MOD｜是｜否｜下取整

FUNCTION REM｜是｜是｜截断

CoffeeScript｜是｜否｜截断

是｜否｜下取整

ColdFusion｜, MOD｜是｜否｜截断

Common Intermediate Language｜(有符号)｜是｜是｜截断

rem.un (无符号)｜是｜否｜不适用

Common Lisp｜是｜是｜下取整

是｜是｜截断

Crystal语言｜, modulo｜是｜是｜下取整

remainder｜是｜是｜截断

D｜是｜是｜截断

Dart｜是｜是｜欧几里得式

remainder｜是｜是｜截断

Eiffel｜是｜否｜截断

Elixir｜rem/2｜是｜否｜截断

Integer.mod/2｜是｜否｜下取整

Elm｜modBy｜是｜否｜下取整

remainderBy｜是｜否｜截断

Erlang｜是｜否｜截断

math:fmod/2｜否｜是｜截断 (同于C)

Euphoria｜是｜否｜下取整

remainder｜是｜否｜截断

F#｜是｜是｜截断

Math.IEEERemainder｜否｜是｜修约

Factor｜是｜否｜截断

FileMaker｜Mod｜是｜否｜下取整

Forth｜是｜否｜实现定义

fm/mod｜是｜否｜下取整

sm/rem｜是｜否｜截断

Fortran｜是｜是｜截断

modulo｜是｜是｜下取整

Frink语言｜是｜否｜下取整

Full BASIC｜MOD｜是｜是｜下取整

REMAINDER｜是｜是｜截断

GLSL｜是｜否｜未定义

否｜是｜下取整

GameMaker Studio (GML)｜,｜是｜否｜截断

GDScript (Godot)｜是｜否｜截断

fmod｜否｜是｜截断

posmod｜是｜否｜欧几里得式

fposmod｜否｜是｜欧几里得式

Go｜是｜否｜截断

math.Mod｜否｜是｜截断

big.Int.Mod｜是｜否｜欧几里得式

big.Int.Rem｜是｜否｜截断

Groovy｜是｜否｜截断

Haskell｜是｜否｜下取整

是｜否｜截断

Data.Fixed.mod' (GHC)｜否｜是｜下取整

Haxe｜是｜否｜截断

HLSL｜是｜是｜未定义

J｜`|`｜是｜否｜下取整

Java｜是｜是｜截断

Math.floorMod｜是｜否｜下取整

JavaScriptTypeScript｜是｜是｜截断

Julia｜是｜是｜下取整

,｜是｜是｜截断

Kotlin｜,｜是｜是｜截断

是｜是｜下取整

ksh｜是｜否｜截断 (同于POSIX sh)

fmod｜否｜是｜截断

LabVIEW｜是｜是｜截断

LibreOffice｜=MOD｜是｜否｜下取整

Logo｜MODULO｜是｜否｜下取整

REMAINDER｜是｜否｜截断

Lua 5｜是｜是｜下取整

Lua 4｜mod(x,y)｜是｜是｜截断

Liberty BASIC｜MOD｜是｜否｜截断

Mathcad｜mod(x,y)｜是｜否｜下取整

Maple｜e mod m (默认), modp(e, m)｜是｜否｜欧几里得式

mods(e, m)｜是｜否｜修约

frem(e, m)｜是｜是｜修约

Mathematica｜Moda, b｜是｜否｜下取整

MATLAB｜是｜否｜下取整

是｜否｜截断

Maxima｜是｜否｜下取整

remainder｜是｜否｜截断

Maya嵌入语言｜是｜否｜截断

Microsoft Excel｜=MOD｜是｜是｜下取整

Minitab｜MOD｜是｜否｜下取整

Modula-2｜MOD｜是｜否｜下取整

REM｜是｜否｜截断

MUMPS｜是｜否｜下取整

Netwide Assembler (NASM, NASMX)｜, (无符号)｜是｜否｜不适用

(有符号)｜是｜否｜实现定义

Nim｜是｜否｜截断

Oberon｜MOD｜是｜否｜类似下取整

Objective-C｜是｜否｜截断 (同于C99)

Object Pascal, Delphi｜是｜否｜截断

OCaml｜是｜否｜截断

mod_float｜否｜是｜截断

Occam｜是｜否｜截断

Pascal (ISO-7185和ISO-10206)｜是｜否｜类似欧几里得式

Perl｜是｜否｜下取整

POSIX::fmod｜否｜是｜截断

PHP｜是｜否｜截断

fmod｜否｜是｜截断

PIC BASIC Pro｜是｜否｜截断

PL/I｜是｜否｜下取整 (ANSI PL/I)

PowerShell｜是｜否｜截断

Programming Code (PRC (Palm OS))｜MATH.OP - 'MOD; (\)'｜是｜否｜未定义

OpenEdge高级商务语言｜modulo｜是｜否｜截断

Prolog (ISO 1995)｜是｜否｜下取整

是｜否｜截断

PureBasic｜, Mod(x,y)｜是｜否｜截断

PureScript｜`mod`｜是｜否｜欧几里得式

Pure Data｜是｜否｜截断 (同于C)

是｜否｜下取整

Python｜是｜是｜下取整

math.fmod｜否｜是｜截断

math.remainder｜否｜是｜修约

Q#｜是｜否｜截断

R｜是｜是｜下取整

Racket｜modulo｜是｜否｜下取整

remainder｜是｜否｜截断

Raku｜否｜是｜下取整

RealBasic｜MOD｜是｜否｜截断

Reason｜是｜否｜截断

Rexx｜是｜是｜截断

IBM RPG｜%REM｜是｜否｜截断

Ruby｜, modulo｜是｜是｜下取整

remainder｜是｜是｜截断

Rust｜是｜是｜截断

rem_euclid｜是｜是｜欧几里得式

SAS｜MOD｜是｜否｜截断

Scala｜是｜是｜截断

Scheme｜modulo｜是｜否｜下取整

remainder｜是｜否｜截断

Scheme R6RS｜是｜否｜欧几里得式

mod0｜是｜否｜修约

flmod｜否｜是｜欧几里得式

flmod0｜否｜是｜修约

Scratch｜是｜是｜下取整

Seed7｜是｜是｜下取整

是｜是｜截断

SenseTalk｜modulo｜是｜否｜下取整

是｜否｜截断

Unix shell (包括bash、ash等。)｜是｜否｜截断 (同于C)

Smalltalk｜是｜否｜下取整

rem:｜是｜否｜截断

Snap!｜是｜否｜下取整

Parallax Propeller｜是｜否｜下取整

Solidity｜是｜否｜下取整

SQL (SQL:1999)｜mod(x,y)｜是｜否｜截断

SQL (SQL:2011)｜是｜否｜截断

Standard ML｜是｜否｜下取整

Int.rem｜是｜否｜截断

Real.rem｜否｜是｜截断

Stata｜mod(x,y)｜是｜否｜欧几里得式

Swift｜是｜否｜截断

remainder(dividingBy:)｜否｜是｜修约

truncatingRemainder(dividingBy:)｜否｜是｜截断

Tcl｜是｜否｜下取整

fmod｜否｜是｜截断 (同于C)

tcsh｜是｜否｜截断

Torque (游戏引擎)｜是｜否｜截断

Turing语言｜是｜否｜下取整

Verilog (2001)｜是｜否｜截断

VHDL｜是｜否｜下取整

是｜否｜截断

VimL｜是｜否｜截断

Visual Basic｜Mod｜是｜否｜截断

WebAssembly｜i32.rem_u, i64.rem_u (无符号)｜是｜否｜不适用

i32.rem_s, i64.rem_s (有符号)｜是｜否｜截断

x86汇编语言｜DIV(无符号)｜是｜否｜不适用

IDIV(有符号)｜是｜否｜截断

XBase++｜是｜是｜截断

Mod｜是｜是｜下取整

Zig｜, @mod, @rem｜是｜是｜截断

Z3定理证明器｜,｜是｜否｜欧几里得式

此外，很多计算机系统提供divmod功能，它同时产生商和余数。例子x86架构的IDIV指令，C编程语言的div函数，和Python的divmod函数。

## 常见错误

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

举个例子：如果需要判断一个整数是否为奇数，有人可能会测试这个数除 2 的余数是否为 1：

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

但在一个取模结果与被除数符号相同的编程语言里，这样做是错的。因为当被除数 n 是奇数且为负数时， $n \bmod 2$ 得到 −1，此时函数返回“假”。

一种正确的实现是测试取模结果是否为 0，因为余数为 0 时没有符号的问题：

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

或者考虑余数的符号，有两种情况：余数可能为 1 或 -1。

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

## 性能问题

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

例如：2 的 n 次幂的模，可以通过逐位与运算实现：

`x % 2<sup>n</sup> == x & (2<sup>n</sup> - 1)`

例子，假定 x 为正数：

`x % 2 == x & 1`

`x % 4 == x & 3`

`x % 8 == x & 7`

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

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

## 用途

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

## 参见

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