1 模运算加乘

模运算的“公理”（结构与基本性质），可以从两层来说明：

一、关于“同余”关系（模 n 的同余 ≡）——它是一个等价关系并与加、乘兼容：

自反性：a ≡ a (mod n)。

对称性：若 a ≡ b (mod n)，则 b ≡ a (mod n)。

传递性：若 a ≡ b (mod n) 且 b ≡ c (mod n)，则 a ≡ c (mod n)。

兼容性（保运算）：

若 a ≡ b (mod n) 且 c ≡ d (mod n)，则 a + c ≡ b + d (mod n)。

若 a ≡ b (mod n) 且 c ≡ d (mod n)，则 a * c ≡ b * d (mod n)。

2 常规代数公理

所谓常规代数公理，就是关于整数模 n 所得到的代数结构 𝑍𝑛（即取模后的剩余类集合）的常规代数公理：

对加法：封闭性、结合律、交换律、有加法单位元 0、每个元素有加法逆元（-a）。

对乘法：封闭性、结合律、交换律（整数模 n 下乘法仍交换）、有乘法单位元 1。

分配律：乘法对加法分配。

以上说明 𝑍𝑛 是一个环（ring）。
若 n 是素数，则每个非零元素都有乘法逆元， 𝑍𝑝 是有限域（field）。

补充重要概念（常被当作“公理化”使用的事实）：

可逆性（乘法逆元）：在 𝑍𝑛 中，元素 a 在模 n 下可逆当且仅当 gcd(a, n) = 1。逆元可以用扩展欧几里得算法求出。

模除：不能总是直接做；只有当除数在模 n 下有逆元时才相当于乘以逆元。

模幂：指数可用快速幂算法在对数时间内计算（模指数运算的基础）。

中国剩余定理（CRT）：如果 n = n1n2… 且互质，则模 n 的问题可以等价分解到模 n1, n2, … 上求解并合并解。

• 经典使用场景（与每个场景常用的性质）

同余判断 / 整除检测

场景：判断某数是否能被 k 整除，或计算最后几位（如模 10^k）。

用到：模运算的基本定义、兼容性。

哈希 / 环上的环形缓冲 / 索引循环

场景：数组环索引 i = (i+1) mod n，环形缓冲队列。

用到：模加、取余。

加密与公钥密码学（RSA、ElGamal、DH）

场景：大整数模幂、使用模逆、素模下的乘法群。

用到：模幂（快速幂），扩展欧几里得求逆，欧拉函数、费马小定理、CRT（用来加速解密）。

• 求逆与解线性同余方程

场景：求 a x ≡ b (mod n) 的解。

用到：gcd 判定，可逆性与扩展欧几里得算法。

• 中国剩余定理（CRT）

场景：把大模问题拆成多个小模并合并，或序列重建（如并行计算、日历问题）。

用到：互质模、逆元、合并公式。

伪随机数 / 随机散列（LCG）

场景：线性同余生成器 X_{n+1} = (a X_n + c) mod m。

用到：模加与模乘。

组合数学中的模计数

场景：对大数取模（如 10^9+7）计算组合数、DP 保持不溢出。

用到：模乘、模逆（当模为质数时用费马小定理求逆）。

3 小结

扩展欧几里得（求逆）：求 x 使 a x + n y = gcd(a,n)。若 gcd=1，则 x 即为模逆（取 x mod n）。

快速幂（模幂）：二分指数，用 O(log e) 时间计算 a^e mod n。

CRT 合并（对两模互质的情况）：若 x ≡ a (mod n1)、x ≡ b (mod n2)，令 m1 = n2，m2 = n1，计算逆元并合并：
x = a + ( (b - a) * inv(n1 mod n2) mod n2 ) * n1（最后对 n1*n2 取模）。