模算术是一种算术体系,按照整数除以某个固定正整数所得的余数来比较整数并进行运算,这个固定正整数称为模数。相差模数的整数倍的数被视为等价。因此,运算呈现出“循环回绕”的特征,而不是沿数轴无限递增。模算术为数论提供了基本语言,也是密码学中许多重要构造的基础。(cs.cornell.edu)
同余与余数
对于正整数 ,记号
表示 整除 ,等价地说,存在整数 ,使得 。因此,,因为两者之差为 。负整数也有剩余:。同余式描述的是整数之间的一种关系,而不是通常意义上的相等。(cs.cornell.edu)
根据带余除法,每个整数都可以唯一地表示为 ,其中 。数 称为该整数模 的最小非负剩余。因此,同余的整数具有相同的余数。表达式 通常表示这个特定的余数,而同余式中的“”则用于指明所采用的同余关系。(cs.cornell.edu)
十二小时制的钟表可以说明这一概念:从十点往后推五小时得到三点,因为 。钟面上的十二对应剩余零。这个类比解释了循环回绕的加法,不过模算术还支持乘法及更一般的代数运算。(pi.math.cornell.edu)
运算法则
同余关系与加法、减法和乘法相容。如果 且 ,那么
因此,可以在运算过程中对中间结果取模 ,而不改变最终的剩余。例如,在模七的运算中,。先取模往往能显著减小运算中涉及的数。(cs.cornell.edu)
通过反复相乘,还可得出:对于任意非负整数 ,都有 。这些规则也适用于计算任意整系数多项式的值。不过,一般不能对指数按同一个模数取模:,但 。对指数进行约化需要另外的条件和定理。(cs.cornell.edu)
剩余类与代数结构
模 同余是一种等价关系:它具有自反性、对称性和传递性。它将全体整数划分为 个剩余类。包含 的剩余类为
这些剩余类组成的集合记作 ,也写作 。加法和乘法分别定义为 和 ;同余运算法则保证这些定义不依赖于所选的代表元。(cs.cornell.edu)
在抽象代数中,这一结构是一个有单位元的交换环(数学)。它的加法结构是一个循环群,因此也与群论相联系。如果 是素数,每个非零剩余类都可逆,所以这个环是一个域(数学),具体而言,是一个含有 个元素的有限域。若模数为合数,则存在乘积为零的非零剩余类:例如在模六的运算中,。(cs.cornell.edu)
逆元与线性同余方程
的一个模乘法逆元是满足 的整数 。它存在的充要条件是最大公约数 等于一。扩展欧几里得算法可以求出满足 的整数 ;对这个等式两边取模 ,即可得到逆元。例如,三在模七下的逆元是五。(math.stanford.edu)
因此,这里的除法是指乘以逆元,而不是普通的整数除法。当因子不可逆时,约去该因子可能不成立:,但 。更一般地,约去因子 后,模数应变为 。(cs.cornell.edu)
线性同余方程 有解的充要条件是 整除 。若有解,则恰有 个模 意义下互不相同的解。例如, 有两个解: 和 。将系数和模数都除以 ,再应用逆元存在的判定条件,即可得到这些结论。(math.stanford.edu)
基本定理
费马小定理指出,对于素数 ,有 。如果 不整除 ,则可写成 。欧拉定理推广了后一结论:
这里的欧拉函数 表示从一到 的整数中与 互素的整数个数。(math.stanford.edu)
中国剩余定理可以将模数两两互素的同余式合并。对于给定的同余方程组 ,该定理保证其解在模 的意义下恰好构成一个剩余类。因此, 和 合起来可得 。(math.stanford.edu)
历史发展与应用
卡尔·弗里德里希·高斯在1801年出版的《算术研究》中系统论述了同余理论。该书开篇各节讨论了一般的同余关系、线性同余方程以及幂的剩余,为后续研究奠定了框架。(e-rara.ch)
在计算机科学中,模运算用于哈希表索引、校验位和伪随机序列。模运算也能解释十进制数的整除判别法:由于 ,一个整数与其各位数字之和模九同余。(cs.cornell.edu)
RSA密码系统采用模幂运算,其模数由两个素数相乘得到。它的基本数学变换为 ,并用与之相关的私钥指数执行逆变换。要实现安全加密,除了这一算术运算,还需要额外的编码和填充机制。(cs.cornell.edu)
参考来源
- cs.cornell.edu/courses/cs2800/2017sp/handouts/pass_tseng_discmath.pdfcs.cornell.edu
- cs.cornell.edu/courses/cs2800/2016sp/lectures/lec12-modular.htmlcs.cornell.edu
- pi.math.cornell.edu/~mec/Summer2008/lundell/lecture2.htmlpi.math.cornell.edu
- cs.cornell.edu/courses/cs2800/2017sp/lectures/lec32-modular.htmlcs.cornell.edu
- math.stanford.edu/~vakil/putnam04/04putnam2.pdfmath.stanford.edu
- e-rara.ch/zut/content/structure/1254642e-rara.ch
- cs.cornell.edu/courses/cs5431/2017sp/Lec4-RSA.pdfcs.cornell.edu