中国剩余定理详解 · 从韩信点兵到密码学
把大数拆解开，用同余方程组破解“局部规则不同，整体固定”的数学难题。深入理解中国剩余定理的构造与妙用。
? 起源 · 韩信点兵
《孙子算经》中“物不知数”问题：今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？这正是中国剩余定理的雏形。它解决了一类同余方程组，要求模数两两互质。
历史经典 明朝程大位编成歌诀“三人同行七十稀，五树梅花廿一枝，七子团圆正半月，除百零五便得知”。
? 核心思想
中国剩余定理（CRT）表明：若整数n₁, n₂,…, nₖ两两互质，则对任意余数a₁,…,aₖ，存在唯一解x模N=n₁n₂…nₖ。它通过构造加权和实现“局部满足”。
x ≡ a₂ (mod n₂)
… 通用解：x = Σ aᵢ · Mᵢ · tᵢ (mod N)
? 原理拆解与构造
✅ 标准中国剩余定理 (模两两互质)
给定模数 m₁=3, m₂=5, m₃=7，余数 a₁=2, a₂=3, a₃=2。计算总模 M=3×5×7=105。然后分别计算 M₁=35, M₂=21, M₃=15。求逆元：35×2≡1 mod3，21×1≡1 mod5，15×1≡1 mod7。解为 x = (2×35×2 + 3×21×1 + 2×15×1) mod 105 = 23。
- ◆ Mᵢ = M / mᵢ ，确保与其他模数关联。
- ◆ 求 tᵢ 使得 Mᵢ·tᵢ ≡ 1 (mod mᵢ)。
- ◆ 最终解 x₀ = Σ aᵢ·Mᵢ·tᵢ，通解 x = x₀ + k·M。
⚡ 扩展：模数不互质的情况
当模数不互质时，需合并方程。例如 x≡3 mod6, x≡5 mod10。先检查一致性：gcd(6,10)=2，且3≡5 mod2？3 mod2=1,5 mod2=1，一致。合并后模数为lcm(6,10)=30，解为x≡23 mod30。若余数不一致则无解。
其中 t 满足 m₁·t ≡ a₂-a₁ (mod m₂/gcd)
这在RSA密钥生成和大数运算中极为关键，避免直接处理巨大数字。
? 构造性证明
设N = ∏ nᵢ，定义Nᵢ = N/nᵢ。由于nᵢ互质，gcd(Nᵢ, nᵢ)=1，故存在逆元 yᵢ使 Nᵢ·yᵢ ≡ 1 (mod nᵢ)。令 x = Σ aᵢ Nᵢ yᵢ。对任意模nⱼ，当i≠j时Nᵢ包含因子nⱼ，故项为0；i=j时贡献aⱼ。因此x满足所有同余式。唯一性由模N保证。
直观理解：每个分量只对自己模数贡献余数，对其他模数“透明”。
⏳ 经典例题与时间轴
- 公元3世纪 · 物不知数 —— 首次记载中国剩余定理原型。解为23，验证：23 mod3=2, mod5=3, mod7=2。
- 1247年 · 秦九韶大衍求一术 —— 系统化求解一次同余式组，提出“大衍总数术”，比欧洲早500余年。
- 现代密码学 · RSA加速 —— 利用CRT将解密速度提升约4倍。计算 c^d mod pq 分解为 mod p 和 mod q 分别计算再合并。
- 算法竞赛 · 模数非互质 —— 使用扩展中国剩余定理处理任意模数线性同余方程组，时间复杂度O(n log M)。
? 示例1：古堡钥匙模型
钥匙编号满足：x ≡ 1 mod 2, x ≡ 2 mod 3, x ≡ 3 mod 5。模数互质，M=30。M₁=15,t₁=1; M₂=10,t₂=1; M₃=6,t₃=1。解x=(1·15·1+2·10·1+3·6·1)=53 ≡ 23 mod30。钥匙编号23符合规则。
? 示例2：任务分配问题
总工作量W满足：W mod4=1, W mod5=2, W mod9=3。模数4,5,9互质。M=180。计算得W≡157 mod180。最小正整数解157。可验证157%4=1,157%5=2,157%9=4? 需检查：157÷9=17余4，但要求余3，说明需调整。正确计算后应为W=157？重新计算：M₁=45,t₁=1(45≡1mod4),M₂=36,t₂=1(36≡1mod5),M₃=20,t₃=5(20×5=100≡1mod9)。W=1·45·1+2·36·1+3·20·5=45+72+300=417≡57 mod180。57验证：57%4=1,57%5=2,57%9=3。正确！
? 现代应用 & 网友们还关心
? RSA加密中的CRT
RSA私钥操作使用中国剩余定理将模幂运算分解为两个较小模数。解密 m = c^d mod n (n=pq) 转换为计算 m₁=c^d mod p 和 m₂=c^d mod q，再用CRT合并。速度提升显著。
关键：预计算 dP=d mod (p-1), dQ=d mod (q-1), qInv=q⁻¹ mod p。
?️ 哈希与编码
在分布式存储和纠错码中，CRT用于重构丢失数据。通过多个互质模数的余数表示大整数，实现冗余恢复。
? 网友们还关心
两者本质都是构造线性组合满足局部条件，CRT可视为模算术下的插值。
对于任意两个方程，必须满足a_i ≡ a_j (mod gcd(n_i,n_j))，否则无解。
是的，多项式版本的中国剩余定理广泛应用于信号处理和编码理论。
通过辗转相除求逆元，例如求35 mod3的逆：35=11×3+2,3=1×2+1，回代得逆元2。
因最早见于中国南北朝数学著作，由西方数学家高斯重新发现并命名。
基于中国剩余定理的阈值方案将秘密拆分为多个余数，只有足够份额才能恢复。
? 深度示例与变体
问题：求最小正整数x满足 x≡1 mod2, x≡2 mod5, x≡3 mod7, x≡4 mod9。模数两两互质，M=630。分别计算Mᵢ和逆元，得到x=157? 详细：M₁=315,t₁=1;M₂=126,t₂=1;M₃=90,t₃=4(90×4=360≡1mod7);M₄=70,t₄=4(70×4=280≡1mod9)。x=1·315·1+2·126·1+3·90·4+4·70·4=315+252+1080+1120=2767≡247 mod630。验证247%2=1,247%5=2,247%7=2? 需检查7×35=245余2，要求余3，说明计算有误。正确逆元：90 mod7的逆元为4(90≡6,6×4=24≡3? 重新求：90≡6 mod7,6×6=36≡1 mod7，逆元应为6)。调整后x=1·315·1+2·126·1+3·90·6+4·70·4=315+252+1620+1120=3307≡157 mod630。157%7=3正确。故解为157。
模数非互质示例：x≡2 mod4, x≡4 mod6。gcd(4,6)=2，检查2≡4 mod2成立。合并：lcm=12。由x=2+4t，代入第二个：2+4t≡4 mod6 → 4t≡2 mod6 → 2t≡1 mod3 → t≡2 mod3。取t=2得x=10。通解x≡10 mod12。验证10%4=2,10%6=4。
另一个常见例子：x≡3 mod8, x≡7 mod12。gcd=4,3≡7 mod4? 3 mod4=3,7 mod4=3一致。lcm=24。x=3+8t，代入12模：3+8t≡7 mod12 →8t≡4 mod12 →2t≡1 mod3 →t≡2 mod3。t=2,x=19。通解19+24k。
? 思维拓展：同余与群论
中国剩余定理在抽象代数中体现为环的直积分解。Z/mZ ≅ Z/m₁Z × … × Z/mₖZ 当mᵢ互质。这为快速傅里叶变换和数论变换提供理论基础。
? 复杂度与实现
使用扩展欧几里得算法求逆元，整体时间复杂度O(k log M)。在算法竞赛中常与Lucas定理、组合数取模结合。