余数定理

余数定理 (Chinese Remainder Theorem, CRT)

余数定理→数论/抽象代数核心→描述同余方程组解的存在唯一性：给定两两互质模数$m_1,\ldots,m_k$→任意余数$a_1,\ldots,a_k$→存在唯一解模$M=\prod m_i$。核等式：

→$M_i=M/m_i$→$y_i$为$M_i$模$m_i$的乘法逆元：$M_i y_i\equiv 1\pmod{m_i}$。

历史与直观

源《孙子算经》"物不知数"：三三数余二→五五数余三→七七数余二→求物数。解：$x\equiv 23\pmod{105}$。直观：若仅一式$x\equiv a\pmod{m}$→无限多解$a+tm$；多式联立→筛选交集→互质性保证交集非空→模$M$内唯一。核思想：分解→独立求解→合成→大模数问题化为互质小模数→逐一攻破→合而得整体解。

环论本质

代数深层：中国剩余定理=环同构。映射$f:\mathbb{Z}/M\mathbb{Z}\to\mathbb{Z}/m_1\mathbb{Z}\times\cdots\times\mathbb{Z}/m_k\mathbb{Z}$，$f(x\bmod M)=(x\bmod m_1,\ldots,x\bmod m_k)$→当$m_i$两两互质→$f$为环同构→既单射又满射→解存在(满射)且唯一(单射)。泛化至一般交换环→理想互质条件→CRT推广至理想理论。

构造性证明

步骤一：算$M=\prod m_i$→$M_i=M/m_i$→$M_i$与$m_i$互质→由贝祖等式→∃$y_i$使$M_i y_i\equiv 1\pmod{m_i}$(扩展欧几里得算法)。步骤二：构特解$x_0=\sum a_i M_i y_i$→验：模$m_j$→$i\neq j$项$M_i$含因子$m_j$→消→仅剩$a_j M_j y_j\equiv a_j\cdot1=a_j\pmod{m_j}$。步骤三：通解$x=x_0+tM(t\in\mathbb{Z})$→模$M$内唯一。证完。

非互质情况

若$\gcd(m_i,m_j)=d>1$→须满足相容条件：$a_i\equiv a_j\pmod{d}$对所有$i,j$→否则无解。可解时→合并等价模→逐步约化为互质情形→仍可用CRT。实际上→若$\gcd(m_1,m_2)=d$→两式可并为$x\equiv a\pmod{\operatorname{lcm}(m_1,m_2)}$当$a_1\equiv a_2\pmod{d}$→迭代至互质或判无解。

计算加速与RSA

CRT→模幂加速核：计算$c^d\bmod n$($n=pq$→RSA)→分算$c^d\bmod p$与$c^d\bmod q$→各速约4倍(模小/指数小)→CRT合二结果→总提速约4倍→RSA解密/签名标配(CRT-RSA)。另→Garner算法：逐步合并同余式→避免大模数逆元预计算→高效硬件实现。

拉格朗日插值联系

CRT与拉格朗日插值结构同源：插值→给定点$(x_i,y_i)$求通过多→CRT→给定余数求满足整数。核：Lagrange基函数$L_i(x)=\prod_{j\neq i}\frac{x-x_j}{x_i-x_j}$↔CRT中$M_i y_i$→皆"在某点/模为1→其余为零"→线性组合得解→本质：商空间直和分解→两个对偶基实例。

秘密共享

Asmuth-Bloom方案：CRT变体→$(t,n)$门限→秘密$S$编码为同余方程组→选模数$m_0<m_1<\cdots<m_n$使任意$t$个$m_i$之积$>m_0\cdot$任意$t-1$个→恢复$S$需至少$t$份子密钥→CRT合成→不足$t$份→模积不足→无法唯一确定→信息论安全。

推广

①多项式CRT：多项式环中→模多项式两两互质→CRT成立→快速傅里叶变换(FFT)多点求值/插值→信号处理核。②一般交换环：理想$I_1,\ldots,I_k$两两互质($I_i+I_j=R$)→$R/\bigcap I_i\cong R/I_1\times\cdots\times R/I_k$。③戴德金域→分式理想CRT分解→代数数论基石。④编码理论→Reed-Solomon码解码→CRT视角→纠错定位。余数定理→对整数、多项式、理想统一→"分而治之"数学范本→数论/代数/计算/密码跨界枢纽。