中国剩余定理与插值多项式关系的探究

2011-02-10 01:57黄湧辉

长江大学学报(自科版) 2011年13期

黄湧辉

（华南师范大学数学科学学院，广东广州510631）

在我国古代数学名著《孙子算经》有这样一个 “物不知数”问题，“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？”，这就是著名的中国剩余定理。此外，插值法也是一种古老的数学方法。早在1000多年前，我国科学家在研究历法时就应用了线性插值和二次插值，但它基本理论却在微积分产生以后才逐步完善的。下面，笔者研究中国剩余定理与插值法之间的关系，并给出数值例子验证了所得的结论。

1 n次拉格朗日（Lagrange）插值多项式

对于n＋1个互不相同的插值节点xi，i＝0，1，2，…，n，由n次插值多项式的惟一性，可对每个插值节点xi作出相应的n次插值基函数li（x），i＝0，1，2，…，n。要求x0，x1，…，xi－1，xi＋1，…，xn是li（x）的零点，因此可设：

因而有：

作其组合：

那么Ln（x）不高于n次且满足Ln（xi）＝f（xi），i＝0，1，2，…，n，故Ln（x）是关于插值点x0，x1，…，xn的插值多项式，这种插值形式称为n次拉格朗日（Lagrange）插值多项式。

2 中国剩余定理

定理1 （中国剩余定理［1］）设m1，m2，…，mn是两两互素的自然数，令：

则方程组：

的解为：

式中，M′i是整数，使得 M′iMi≡1（mod mi），i＝1，2，…，n。该方程有且仅有一个小于m 的非负整数解。

推论1［1］若n≥2，m1，m2，…，mn为整数，则同余方程组有解的充要条件是对任意的i，j有（mi，mj）｜bi－bj，其中，（mi，mj）为mi，mj的最大公因数，i，j＝1，2，…，n。

由中国剩余定理可得到如下结论：

定理2 设m1（x），m2（x），…，mn（x）是n个两两互素的且次数n≥1多项式，任给n个多项式a1（x），a2（x），…，an（x），则一定存在多项式f（x），使得：

并且f（x）关于m（x）是唯一确定，其中m（x）＝m1（x）m2（x）…mn（x）。

证明先对方程组中的式（1）和式（2）进行讨论。由于m1（x）和m2（x）互素，所以利用辗转相除法找到p（x）和q（x），使得p（x）m1（x）＋q（x）m2（x）＝1。两边同时乘以a1（x）－a2（x）得：

即：

也即：

故：

由此可得：

故：

同理可得到方程组中的其余式子。因而定理2得证。

3 关系探究

记mi（x）＝x－bi∈Q［x］，i＝1，2，…，n，其中，bi是互不相等的常数。由于mi（x），（i＝1，2，…，n）为有理数域Q［x］上的不可约多项式，从而mi（x）是两两互素的多项式。由于mi（x）≡mi（bi）（mod（x－bi）），（i＝1，2，…，n），由中国剩余定理知，一定存在多项式f（x），使得：