[科普中国]-模除

模除是一种不具交换性的二元运算。

简介

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

给定两个正整数：被除数a和除数n，amodulon(缩写为amodn)得到的是使用欧几里德除法时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（amod 1恒等于 0；amod 0则是未定义的，在编程语言里可能会导致除零错误）。 有关概念在数论中的应用请参阅模算数。

当a和n均为负数时，通常的定义就不适用了，不同的编程语言对结果有不同的处理。1

用途

取模运算可用于判断一个数是否能被另一个数整除。对 2 取模即可判断整数的奇偶性；从 2 到 n-1 取模则可判断一个数是否为质数。

进制之间的转换。

用于求取最大公约数的辗转相除法使用取模运算。

密码学中的应用：从古老的凯撒密码到现代常用的RSA、椭圆曲线密码，它们的实现过程均使用了取模运算。

记号

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

a% n

或

a mod n

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

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

等价性

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

恒等式：

(amodn) modn=amodn

对所有的正数x有：nmodn= 0

如果p是一个质数，且不为b的因数，此时由费马小定理有：abmodp=amodp

逆运算：

[(−amodn) + (amodn)] modn= 0.

bmodn表示模反元素。当且仅当b与n互质时，等式左侧有定义：[(bmodn)(bmodn)] modn= 1。

分配律：

(a+b) modn= [(amodn) + (bmodn)] modn

abmodn= [(amodn)(bmodn)] modn

dmod (abc) = (dmoda) +a[(d\a) modb] +ab[(d\a\b) modc]，符号\是欧几里德除法中的除法操作符，运算结果为商

cmod (a+b) = (cmoda) + [bc\ (a+b)] modb- [bc\ (a+b)] moda.

除法定义：仅当式子右侧有定义时，即b、n互质时有：abmodn= [(amodn)(bmodn)] modn，其他情况为未定义的。

乘法逆元：[(abmodn)(bmodn)] modn=amodn.2

本词条内容贡献者为:

程鹏 - 副教授 - 西南大学