概念

同余理论

模 n 运算把整数划分为有限个剩余类并构成环，中国剩余定理给出多个模同时成立时的唯一解，是密码学与数论算法的基础。

阅读路径

参考可汗学院 Get ready 机制：先修概念 → 当前概念 → 进阶概念，✓ 表示已读。

同余理论数系理论

01定义

同余理论研究模

n

运算：整数按除以

n

的余数分成

n

个剩余类，构成环

\mathbb{Z}/n\mathbb{Z}

。中国剩余定理给出多个模同时约束下的唯一解，是密码学与数论算法的基础。

模 4 剩余类：整数按余数分为 4 格成环

$\mathbb{Z}/n\mathbb{Z}$ 中加减乘按代表元运算且良定； $n$ 为素数时它是域——有限域的最初例子。

模两两互素时，同余方程组 $x\equiv a_i\pmod{n_i}$ 在 $\bmod\,\prod n_i$ 下有唯一解——「韩信点兵」问题的数学表述。

$p$ 为素数则 $a^p\equiv a\pmod p$ ——既是素性检验的工具，也是 RSA 正确性证明的构件。

a\equiv b\pmod n\iff n\mid(a-b)

a^p\equiv a\pmod p\quad(\text{费马小定理})

《孙子算经》（约公元 3-5 世纪）记载「物不知数」问题即中国剩余定理的原型；高斯 1801 年《算术研究》以同余记号与系统化理论统合全部成果。

RSA 用 CRT 加速解密；大整数运算按模分解并行化；计算机散列、循环码、历法周期计算都依赖同余算术。

同余：模 n 乘法表格 (a,b) 颜色 = a·b mod n；n 为素数时每行都是 0..n−1 的排列

模 n7