模算数

模算数或称同余运算（英语：Modular arithmetic）是一个整数的算术系统，其中数字超过一定值后（称为模或余数）后会“卷回”到较小的数值，模算数最早是出现在卡尔·弗里德里希·高斯在1801年出版的《算术研究》一书中。

这个时钟计时方式使用了模数为12的模算数

模算数常见的应用是在十二小时制，将一天分为二个以十二小时计算的单位。假设现在七点，八小时后会是三点。用一般的算术加法，会得到7 + 8 = 15，但在十二小时制中，超过十二小时会归零，不存在“十五点”。类似的情形，若时钟目前是十二时，二十一小时后会是九点，而不是三十三点。小时数超过十二后会再回到一，为模12的模算数系统。依照上述的定义，12和12本身同余，也和0同余，因此12:00的时间也可以称为是0:00，因为模12时，12和0同余。

同余关系

此章节介绍的是mod n的表示法。关于二元的mod运算，请见“模除”。

模算数可以在导入整数的同余关系后，通过经典算数的运算法则来推导模运算的运算法则。若有两个正整数${\displaystyle a}$和${\displaystyle b}$，并且二数的差值${\displaystyle a-b}$为${\displaystyle n}$的整数倍数，我们就可以说${\displaystyle a}$和${\displaystyle b}$在模${\displaystyle n}$下同余。数学式表达为：^[1]

${\displaystyle a\equiv b{\pmod {n}}\,}$

例如

${\displaystyle 38\equiv 14{\pmod {12}}\,}$

因为38 − 14 = 24，是12的倍数。

上述的概念也对负数有效：

${\displaystyle {\begin{aligned}-8&\equiv 7{\pmod {5}}\\2&\equiv -3{\pmod {5}}\\-3&\equiv -8{\pmod {5}}.\end{aligned}}}$

而同余关系也可以用计算带余除法中的余数来理解。若正整数${\displaystyle a}$和${\displaystyle b}$在除以${\displaystyle n}$后的余数相同，${\displaystyle a\equiv b{\bmod {m}}}$。例如：

${\displaystyle 38\equiv 14{\pmod {12}}\,}$

因为38和14除以12时，余数都为2。这是因为38 − 14 = 24是12的整数倍。

运算定律

如果${\displaystyle a\equiv b{\pmod {n}}}$，${\displaystyle p\equiv q{\pmod {n}}}$，${\displaystyle c}$为任何正整数，

那么我们有以下运算定律：^[2]

${\displaystyle a+c\equiv b+c{\pmod {n}}}$

${\displaystyle a-c\equiv b-c{\pmod {n}}}$

${\displaystyle ac\equiv bc{\pmod {n}}}$

${\displaystyle a^{c}\equiv b^{c}{\pmod {n}}}$

${\displaystyle a+p\equiv b+q{\pmod {n}}}$

${\displaystyle ap\equiv bq{\pmod {n}}}$

综上所述，我们在模算数里可以使用除除法以外的任何四则运算。

应用

模算数在数论、群论、环论、纽结理论、抽象代数、计算机代数、密码学、计算机科学及化学中都有使用^[3]，也出现在视觉艺术及音乐。

模算数是数论的基础之一，也提供了群论、环论及抽象代数中一些重要的范例。

模算数也常作为识别码的校验码。例如国际银行账户号码（IBAN）就用模97的余数来避免输入编号时的错误。

在密码学中，模算数是 RSA及迪菲-赫尔曼等公开密钥加密系统的基础，也提到了和 椭圆曲线有关的有限域，用在许多的对称密钥算法中，包括高级加密标准（AES）、国际资料加密算法（IDEA）、及RC4。RSA和迪菲-赫尔曼密钥交换用到了模幂。

在电脑代数中，模算数常用来限制中间计算的整数系数大小，也限制计算中用到的资料。模算数用在多项式分解（英语：polynomial factorization）中（其中所有已知有效率的算法都用到了模算数），而针对整数及有理数的多项式最大公因式（英语：polynomial greatest common divisor）、线性代数及Gröbner基（英语：Gröbner basis），最有效率解法都用到了模算数。

计算机科学中，模算数会以位操作的方式表示，也和其他定长度、循环式的数据结构有关。许多编程语言及计算器中都有模除，而XOR是二个位元在模2下的和。

化学中，表示化合物编号的CAS号，最后一码是校验码，是将CAS号前二位数乘以1、下一位乘以2，再下一位乘以3……，最后对10取余数而得。

音乐上，模12的模算数用在十二平均律的系统中，其中有纯八度及异名同音的情形（例如升音符的C音和降音符的D音会视为是同一个音）。

去九法是徒手计算时快速的检查工具，是以模9的模算数为基础，而且其中最重要的性质是${\displaystyle 10\equiv 1{\pmod {9}}}$。

模7的模算数在许多计算特定日期是星期几的算法中出现，特别是蔡勒公式及判决日法则（英语：doomsday algorithm）中。

模算数也用在像法律（像分配 (政治)）、经济学（像博弈论），若一些社会科学的分析会强调资源的比例分割（英语：Proportional (fair division)）及分配，也会用到模算数。

相关条目

• 布尔环
• 环形缓冲区
• 同余关系
• 除法
• 有限域
• 勒让德符号
• 模幂
• 模反元素
• 模除
• 数论
• 皮萨诺周期（模n下的斐波那契序列）
• 原根
• 二次互反律
• 二次剩余
• 两元素布尔代数
• 和模算数有关的群论主题：
  • 循环群
  • 整数模n乘法群
• 其他和模算数有关的重要定理：
  • 卡迈克尔函数
  • 中国剩余定理
  • 欧拉定理 (数论)
  • 费马小定理
  • 拉格朗日定理 (群论)

参考资料

1. Emanuel Lazar. Math 170 lecture notes (PDF). UPenn: 73. April 30, 2016 [2021-10-23]. （原始内容存档 (PDF)于2021-10-23）.
2. Sandor Lehoczky; Richard Rusczky. David Patrick , 编. the Art of Problem Solving Vol. 1 7. : 44. ISBN 0977304566 （英语）.
3. Sharky Kesa; et al. Modular Arithmetic. Brillant. [2021-10-23]. （原始内容存档于2021-10-26）. 引文格式1维护：显式使用等标签 (link)