模除

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

几乎所有的计算系统中，${\displaystyle n}$  除 ${\displaystyle a}$  得到商 ${\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 年卡尔·弗里德里希·高斯引入模算数时产生的。
• 模幂运算
• 同余