模同余

模同余的出发点是：许多问题只关心余数，不关心整数本身的大小——星期几、时钟指针、奇偶性都是这样。于是我们干脆宣布"相差 $n$ 的倍数的整数是同一个状态"，把无限长的整数轴卷成一个只有 $n$ 个位置的圆环。这个想法能成立的关键在于运算的相容性：两个数各自换成同余的代表后，和与积的变化量仍是 $n$ 的倍数，因此在剩余类上做加法和乘法是良定义的——我们实际上造出了一个有限的环。同余与等式最大的差别在除法：等式两边可以约去任何非零因子，同余却不行，因为一个非零整数在模 $n$ 下可能与 $n$ 有公因子、从而"部分地等于零"。定义中看似简单的整除条件 $n\mid (a-b)$，正是在精确控制哪些信息被抹掉、哪些信息被保留。

正例：$17\equiv 2(\mathrm{mod}5)$，因为 $17-2=15=3\cdot 5$。据此可以立刻算出 ${17}^2\equiv 2^2=4(\mathrm{mod}5)$——相容性允许先取余再运算，这正是快速幂等算法的依据。

消去律失效的标准反例在模 $6$：$2\cdot 1\equiv 2\cdot 4(\mathrm{mod}6)$（两边分别为 $2$ 与 $8$），但 $1\not\equiv 4(\mathrm{mod}6)$。原因是 $gcd(2,6)=2\ne 1$，按消去公式只能得到 $1\equiv 4(\mathrm{mod}3)$，这确实成立。类似地，平方关系不能开方：由 $a^2\equiv b^2(\mathrm{mod}n)$ 一般推不出 $a\equiv \pm b(\mathrm{mod}n)$，例如 $1^2\equiv 4^2(\mathrm{mod}15)$ 而 $4\not\equiv \pm 1(\mathrm{mod}15)$；合数模下一个数可以有多于两个平方根，这一现象正是若干因数分解算法的入口。

边界与记号约定：模数按标准约定取正整数；$n=1$ 时所有整数彼此同余，商环退化为零环。每个剩余类都可选 $0,\dots ,n-1$ 中唯一的标准代表，负数也归入其中（如 $-1\equiv n-1$），代表的选择不影响类本身。此外要区分两种记号：$amodn$ 有时指落在 $[0,n)$ 中的余数值（一个整数），有时指剩余类（一个集合），阅读时需按上下文分辨。

模同余是把无限的整数算术压缩为有限代数结构的枢纽。剩余类环 $\mathbb{Z}/n\mathbb{Z}$ 是最早出现的非平凡有限环；当 $n$ 为素数时它是有限域，其乘法群的结构由 Fermat 小定理公理库费马小定理Fermat's little theorem素数 p 与不被 p 整除的整数 a 满足 a^(p−1)≡1 mod p。与 Euler 函数公理库欧拉函数Euler totient function计数不超过 n 且与 n 互素的正整数的算术函数。刻画。多个互素模数下的同余方程组由中国剩余定理公理库整数中国剩余定理Chinese remainder theorem for integers两两互素模数下的同余方程组在模其乘积意义下有唯一解。拼合，这是 RSA 等公钥体制中大数运算加速的标准手段。模逆的存在性判据 $gcd(a,n)=1$ 及其计算依赖最大公约数公理库最大公约数Greatest common divisor · GCD同时整除两个整数且被所有公约数整除的非负整数。与扩展欧几里得算法。在更抽象的层面，"按理想取商"的构造正是以模同余为原型推广到一般环的，环的同余关系与理想一一对应。