模算术

模算术是一种算术体系，按照整数除以某个固定正整数所得的余数来比较整数并进行运算，这个固定正整数称为模数。相差模数的整数倍的数被视为等价。因此，运算呈现出“循环回绕”的特征，而不是沿数轴无限递增。模算术为数论提供了基本语言，也是密码学中许多重要构造的基础。(cs.cornell.edu)

同余与余数

对于正整数 $n$，记号

表示 $n$ 整除 $a-b$，等价地说，存在整数 $k$，使得 $a-b=kn$。因此，$17\equiv5\pmod{12}$，因为两者之差为 $12$。负整数也有剩余：$-1\equiv11\pmod{12}$。同余式描述的是整数之间的一种关系，而不是通常意义上的相等。(cs.cornell.edu)

根据带余除法，每个整数都可以唯一地表示为 $a=qn+r$，其中 $0\leq r<n$。数 $r$ 称为该整数模 $n$ 的最小非负剩余。因此，同余的整数具有相同的余数。表达式 $a\bmod n$ 通常表示这个特定的余数，而同余式中的“$\pmod n$”则用于指明所采用的同余关系。(cs.cornell.edu)

十二小时制的钟表可以说明这一概念：从十点往后推五小时得到三点，因为 $10+5\equiv3\pmod{12}$。钟面上的十二对应剩余零。这个类比解释了循环回绕的加法，不过模算术还支持乘法及更一般的代数运算。(pi.math.cornell.edu)

运算法则

同余关系与加法、减法和乘法相容。如果 $a\equiv b\pmod n$ 且 $c\equiv d\pmod n$，那么

因此，可以在运算过程中对中间结果取模 $n$，而不改变最终的剩余。例如，在模七的运算中，$19\cdot23\equiv5\cdot2\equiv3$。先取模往往能显著减小运算中涉及的数。(cs.cornell.edu)

通过反复相乘，还可得出：对于任意非负整数 $k$，都有 $a^k\equiv b^k\pmod n$。这些规则也适用于计算任意整系数多项式的值。不过，一般不能对指数按同一个模数取模：$2^4\equiv1\pmod5$，但 $2^{4+5}\equiv2\pmod5$。对指数进行约化需要另外的条件和定理。(cs.cornell.edu)

剩余类与代数结构

模 $n$ 同余是一种等价关系：它具有自反性、对称性和传递性。它将全体整数划分为 $n$ 个剩余类。包含 $a$ 的剩余类为

这些剩余类组成的集合记作 $\mathbb Z/n\mathbb Z$，也写作 $\mathbb Z_n$。加法和乘法分别定义为 $[a]+[b]=[a+b]$ 和 $[a][b]=[ab]$；同余运算法则保证这些定义不依赖于所选的代表元。(cs.cornell.edu)

在抽象代数中，这一结构是一个有单位元的交换环（数学）。它的加法结构是一个循环群，因此也与群论相联系。如果 $n$ 是素数，每个非零剩余类都可逆，所以这个环是一个域（数学），具体而言，是一个含有 $n$ 个元素的有限域。若模数为合数，则存在乘积为零的非零剩余类：例如在模六的运算中，$[2][3]=[0]$。(cs.cornell.edu)

逆元与线性同余方程

$a$ 的一个模乘法逆元是满足 $au\equiv1\pmod n$ 的整数 $u$。它存在的充要条件是最大公约数 $\gcd(a,n)$ 等于一。扩展欧几里得算法可以求出满足 $au+nv=1$ 的整数 $u,v$；对这个等式两边取模 $n$，即可得到逆元。例如，三在模七下的逆元是五。(math.stanford.edu)

因此，这里的除法是指乘以逆元，而不是普通的整数除法。当因子不可逆时，约去该因子可能不成立：$2\cdot1\equiv2\cdot4\pmod6$，但 $1\not\equiv4\pmod6$。更一般地，约去因子 $a$ 后，模数应变为 $n/\gcd(a,n)$。(cs.cornell.edu)

线性同余方程 $ax\equiv b\pmod n$ 有解的充要条件是 $d=\gcd(a,n)$ 整除 $b$。若有解，则恰有 $d$ 个模 $n$ 意义下互不相同的解。例如，$4x\equiv2\pmod6$ 有两个解：$x\equiv2$ 和 $x\equiv5$。将系数和模数都除以 $d$，再应用逆元存在的判定条件，即可得到这些结论。(math.stanford.edu)

基本定理

费马小定理指出，对于素数 $p$，有 $a^p\equiv a\pmod p$。如果 $p$ 不整除 $a$，则可写成 $a^{p-1}\equiv1\pmod p$。欧拉定理推广了后一结论：

这里的欧拉函数 $\varphi(n)$ 表示从一到 $n$ 的整数中与 $n$ 互素的整数个数。(math.stanford.edu)

中国剩余定理可以将模数两两互素的同余式合并。对于给定的同余方程组 $x\equiv a_i\pmod{n_i}$，该定理保证其解在模 $n_1\cdots n_k$ 的意义下恰好构成一个剩余类。因此，$x\equiv2\pmod3$ 和 $x\equiv3\pmod5$ 合起来可得 $x\equiv8\pmod{15}$。(math.stanford.edu)

历史发展与应用

卡尔·弗里德里希·高斯在1801年出版的《算术研究》中系统论述了同余理论。该书开篇各节讨论了一般的同余关系、线性同余方程以及幂的剩余，为后续研究奠定了框架。(e-rara.ch)

在计算机科学中，模运算用于哈希表索引、校验位和伪随机序列。模运算也能解释十进制数的整除判别法：由于 $10\equiv1\pmod9$，一个整数与其各位数字之和模九同余。(cs.cornell.edu)

RSA密码系统采用模幂运算，其模数由两个素数相乘得到。它的基本数学变换为 $c=m^e\bmod n$，并用与之相关的私钥指数执行逆变换。要实现安全加密，除了这一算术运算，还需要额外的编码和填充机制。(cs.cornell.edu)