← 全部笔记

高等代数

多项式的中国剩余定理

文章目录

来源 谢启鸿、姚慕生, 高等代数学习指导书, 第4版, 第5章, 印刷页 246–247, 281, 285. PDF页码 = 印刷页码 + 10。 来源PDF 根据已目视核对的扫描件整理;简洁证明及明确标出的推广为整理者补充。

多项式中国剩余定理 设正次多项式g1,…,gs∈F[x]g_1,\ldots,g_s\in F[x]两两互素,G=∏igiG=\prod_i g_i。给定余式rir_i,存在唯一多项式ff满足deg⁡f<deg⁡G\deg f<\deg G,并对每个ii均满足f≡ri(modgi)f\equiv r_i\pmod{g_i}。

证明。 令Gi=G/giG_i=G/g_i。因为gcd⁡(Gi,gi)=1\gcd(G_i,g_i)=1,可选uiu_i使uiGi≡1(modgi)u_iG_i\equiv1\pmod{g_i}。选择多项式ei=uiGie_i=u_iG_i模gig_i为一,模每个其他gjg_j为零。将∑iriei\sum_i r_ie_i模GG约简便得到存在性。若f,f′f,f'都满足同余式,每个gig_i整除f−f′f-f',两两互素性给出G∣f−f′G\mid f-f',再由次数界得到唯一性(例5.12;这里明确了次数有界的代表元)。

对两个模数,Bézout恒等式up+vq=1up+vq=1给出特别方便的公式 f≡rq up+rp vq(modpq).f\equiv r_q\,up+r_p\,vq\pmod{pq}. 余式乘的是另一个模数。逐一核对同余式,可避免把二者交换(训练解答题4)。

插值是特殊情形

互异节点取 gi=x−aig_i=x-a_i,CRT选择多项式正是Lagrange插值基;完整公式与唯一性证明见 多项式插值与重心形式。重复节点改取 (x−ai)mi(x-a_i)^{m_i},余类编码截断Taylor数据(特征零);与矩阵可逆性的联系见 Vandermonde行列式与插值。本篇保留一般模多项式的构造与相容性条件。

选择多项式变成投影

模GG,选择多项式满足ei2=eie_i^2=e_i,在i≠ji\ne j时满足eiej=0e_ie_j=0,并满足∑iei=1\sum_i e_i=1。这些是同余关系,未必是F[x]F[x]中的等式。若G(T)=0G(T)=0,代入TT使它们成为真正的算子恒等式,见互素多项式与线性变换分解。

若模数不互素,不能任意指定余式:f≡0(modx)f\equiv0\pmod x与f≡1(modx2)f\equiv1\pmod{x^2}相互矛盾。