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

2021-07-19 11:11静,程
关键词:拉格朗插值定理

李 静,程 磊

(信阳学院 数学与统计学院,信阳 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个互异的根,最后通过具体的例子介绍了中国剩余定理在多项式理论中的应用。

猜你喜欢
拉格朗插值定理
J. Liouville定理
滑动式Lagrange与Chebyshev插值方法对BDS精密星历内插及其精度分析
聚焦二项式定理创新题
这样的完美叫“自私”
A Study on English listening status of students in vocational school
拉格朗日的“自私”
基于pade逼近的重心有理混合插值新方法
拉格朗日的“自私”
这样的完美叫“自私”
不同空间特征下插值精度及变化规律研究