模除

(q) 和 餘數 (r) 作為被除數 (a) 的函數時的圖像。左侧是除数为正的情况，右侧除数为负。从上至下分别使用了：向零取整、向下取整和欧几里得除法。]]
模除（），又稱模算術、取模、取模運算等，它得出一个数除以另一个数的余数。给定两个正数：被除数 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 ；而a \bmod 0经常是未定义的，在编程语言里可能会导致除以零错误。当被除数a或除数n为负数时，不同的编程语言对结果有不同的处理。

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

几乎所有的计算系统中，a除以n得到商q和余数r均满足以下式子：
{{NumBlk
| ::
|
\begin{align}
&q \in \mathbb{Z} \\
&a = n q + r \\
&|r|
|
}}

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

{{bulleted list
|很多取模的实现都使用了“截断除法”（），商经由截尾函数来定义，商向零取整，结果等于普通除法所得的小数靠近0方向的第一个整数：
:q=\operatorname{trunc} \left ( \frac{a}{n} \right )
余数和被除数符号一致：
: r = a - n \operatorname{trunc}\left(\frac{a}{n}\right)
|高德纳定义的“下取整除法”（），商经由下取整函数来定义，商总是向负无穷取整，即使商已经是负数：
:q=\left\lfloor\frac{a}{n}\right\rfloor
余数和除数符号一致：
:r = a - n \left\lfloor\frac{a}{n}\right\rfloor
|Raymond T. Boute使用的欧几里得除法定义中，要求满足0 \le r ，在这种情况下：
: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

这里的\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
|Common Lisp的round函数和使用“修约除法”（），商经由修约函数\operatorname{round}（约半成偶）来定义为：
: q = \operatorname{round}\left(\frac{a}{n}\right)
当商为偶数时，余数范围是-\frac{n}{2} \le r \le \frac{n}{2}；当商为奇数时，余数范围是-\frac{n}{2} ：
: r = a - n \operatorname{round}\left(\frac{a}{n}\right)
|Common Lisp的ceiling函数使用“上取整除法”（），商经由上取整函数定义为：
: q = \left\lceil\frac{a}{n}\right\rceil
余数与除数有相反的符号：
: r = a - n \left\lceil\frac{a}{n}\right\rceil
}}

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

在一些没有函数的环境中或许可使用等价的：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.

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

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

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

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

但在一个取模结果与被除数符号相同的编程语言里，这样做是错的。因为当被除数 是奇数且为负数时， 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 % 2 == x & 1
: x % 4 == x & 3
: x % 8 == x & 7

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

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

用途

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

參見

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

脚注
参考文献