中国剩余定理在多项式理论中的应用

李 静，程 磊

(信阳学院 数学与统计学院，信阳 464000)

0 引言

中国古代的“物不知数”问题[1]在国际上被称为“中国剩余定理”，南宋时期的数学家秦九韶给出了求解此类问题的方法“大衍求一术”，这一解法从根本上解决了关于一次同余式组的一般问题。本文首先给出了中国剩余定理的一般形式，接着将这一定理推广到多项式形式，最后通过举例阐述了中国剩余定理在多项式理论中的部分应用。

1 一般形式

定理1(中国剩余定理)[2]设正整数m1,m2,…,mk两两互素，则对于任意的k个正整数a1,a2,…,ak，一次同余方程组

都有整数解，并且在模m=m1m2…mk下这个解是唯一的，即任意两个解都是模m同余的。

2 多项式形式

引理1设某个数域上的多项式p1(x),p2(x),…,pn(x)两两互素，证明存在多项式fi(x)(1≤i≤n)，使得

证因p1(x),p2(x),…,pn(x)是两两互素的，故当j≠i时，

gcd(pj(x),pi(x))=1

因此

从而存在多项式ui(x),vi(x)，使得

定理2(中国剩余定理的多项式形式)[3]设某个数域上的多项式p1(x),p2(x),…,pn(x)两两互素，且它们的次数依次为m1,m2,…,mn。证明对该数域上的任意n个多项式f1(x)，f2(x)，…，fn(x)，存在唯一的次数小于m1+m2+…+mn的多项式f(x)，使得对每个1≤i≤n，均有

f(x)≡fi(x)(modpi(x))

证由引理1可知：对每个1≤i≤n，存在多项式gi(x)，使得

现记

F(x)=f1(x)g1(x)+f2(x)g2(x)+…+

fn(x)gn(x)

此时有

F(x)≡fi(x)(modpi(x))i=1,2,…,n

做如下带余除法运算

其中f(x)的次数

且对每个1≤i≤n，均有

f(x)≡F(x)≡fi(x)(modpi(x))

再证唯一性：

假设g(x)也满足定理中的条件，则

pi(x)|f(x)-g(x) 1≤i≤n

注意到p1(x),p2(x),…,pn(x)是两两互素的，可得

又因为

所以必有

f(x)-g(x)=0

即g(x)=f(x)。

3 在多项式理论中的应用

例1[2]拉格朗日插值公式：设a1,a2,…,an是有理数域(或实数域)上的n个不同的数，则对该数域上的任意n个数b1,b2,…,bn，都存在唯一一个次数小于n的多项式

适合条件

L(ai)=bi，其中 1≤i≤n。

证取多项式

p1(x) =x-a1

p2(x) =x-a2

⋮

pn(x) =x-an

它们是两两互素的。由中国剩余定理，存在唯一的次数小于n的多项式f(x)，使得

f(x)≡bi(modpi(x)) 1≤i≤n

且

当x=ai时，f(ai)=bi1≤i≤n

又因为L(x)满足条件，所以f(x)=L(x)，可得L(x)为所求。

例2证明数域P上的n次多项式f(x)在P里至多有n个互异根。

证若f(x)在P里有n+1个互异根a1,a2,…,an+1，即

f(a1)=0,f(a2)=0,…,f(an+1)=0

则由例1中的拉格朗日插值公式可知：存在唯一一个次数小于n+1的多项式

即f(x)恒为0，与f(x)的次数∂(f(x))=n矛盾，因此结论成立。

例3设多项式f(x)满足

求f(x)被多项式(x-1)(x-2)(x-3)除后的余式。

解将多项式f(x)写成

f(x)=p(x)(x-1)(x-2)(x-3)+r(x)

其中∂(r(x))<3。由条件可得

r(1)=f(1)=4

r(2)=f(2)=8

r(3)=f(3)=16

由例1中的拉格朗日插值公式得

2x2-2x+4

例4设f1(x),f2(x)是数域P上两个多项式，证明：f1(x),f2(x)互素的充分必要条件是对P上任意两个多项式r1(x),r2(x)，都存在P上两个多项式q1(x),q2(x)，使得

q1(x)f1(x)+r1(x)=q2(x)f2(x)+r2(x)

证 充分性

令r1(x)=r2(x)-1，则q1(x)f1(x)-q2(x)f2(x)=1，所以f1(x)与f2(x)互素。

必要性因为f1(x),f2(x)互素，所以存在u1(x),u2(x)∈P[x]，使得

u1(x)f1(x)+u2(x)f2(x)=1

令

g1(x)=u2(x)f2(x)

g2(x)=u1(x)f1(x)

则有

gi(x)≡1(modfi(x))i=1,2

令

F(x)=g1(x)r1(x)+g2(x)r2(x)

则有

F(x)≡ri(x)(modfi(x))i=1,2

所以存在q1(x),q2(x)∈P[x]，使得

F(x)=q1(x)f1(x)+r1(x)=q2(x)f2(x)+r2(x)例5[3]设f(x)除以x2+1、x2+2的余式分别为4x+4,4x+8，求f(x)除以(x2+1)(x2+2)的余式。

解由条件可知

注意到x2+1 与x2+2互素，令

p1(x)=x2+1,p2(x)=x2+2

f1(x)=4x+4,f2(x)=4x+8

所以有

f(x)≡fi(x)(modpi(x))i=1,2

又因为

(-1)(x2+1)+1·(x2+2)=1

令

g1(x)=1·(x2+2)=1·p2(x)

g2(x)=(-1)·(x2+1)=-1·p1(x)

所以有

令

F(x)=f1(x)g1(x)+f2(x)g2(x)

此时有

F(x)≡fi(x)(modpi(x))i=1,2

令

可得

f(x)≡F(x)≡

f1(x)g1(x)+f2(x)g2(x)≡

(4x+4)·1·(x2+2)+

(4x+8)·(-1)·(x2+1)≡

4x-4x2(modp1(x)p2(x))

即f(x)≡4x-4x2(mod(x2+1)(x2+2))

4 结束语

本文介绍了中国剩余定理的多项式形式并给出了证明，运用此定理证明了拉格朗日插值公式的存在性和唯一性，并利用拉格朗日插值公式证明了n次多项式至多有n个互异的根，最后通过具体的例子介绍了中国剩余定理在多项式理论中的应用。