中國剩余定理與插值多項式關系的探究

黃湧輝

（華南師范大學數(shù)學科學學院，廣東 廣州510631）

在我國古代數(shù)學名著 《孫子算經》有這樣一個 “物不知數(shù)”問題，“今有物不知其數(shù)，三三數(shù)之剩二，五五數(shù)之剩三，七七數(shù)之剩二，問物幾何？”，這就是著名的中國剩余定理。此外，插值法也是一種古老的數(shù)學方法。早在1000多年前，我國科學家在研究歷法時就應用了線性插值和二次插值，但它基本理論卻在微積分產生以后才逐步完善的。下面，筆者研究中國剩余定理與插值法之間的關系，并給出數(shù)值例子驗證了所得的結論。

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

對于n＋1個互不相同的插值節(jié)點xi，i＝0，1，2，…，n，由n次插值多項式的惟一性，可對每個插值節(jié)點xi作出相應的n次插值基函數(shù)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是兩兩互素的自然數(shù)，令：

則方程組：

的解為：

式中，M′i是整數(shù)，使得 M′iMi≡1（mod mi），i＝1，2，…，n。該方程有且僅有一個小于m 的非負整數(shù)解。

推論1［1］若n≥2，m1，m2，…，mn為整數(shù)，則同余方程組有解的充要條件是對任意的i，j有（mi，mj）｜bi－bj，其中，（mi，mj）為mi，mj的最大公因數(shù)，i，j＝1，2，…，n。

由中國剩余定理可得到如下結論：

定理2 設m1（x），m2（x），…，mn（x）是n個兩兩互素的且次數(shù)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是互不相等的常數(shù)。由于mi（x），（i＝1，2，…，n）為有理數(shù)域Q［x］上的不可約多項式，從而mi（x）是兩兩互素的多項式。由于mi（x）≡mi（bi）（mod（x－bi）），（i＝1，2，…，n），由中國剩余定理知，一定存在多項式f（x），使得：

式中，ai（i＝1，2，…，n）是任意給定的常數(shù)。當x＝bi時，f（x）≡ai（x）（mod mi（x－bi））化簡為f（bi）＝ai，（i＝1，2，…，n）。由于多項式f（x）的次數(shù)不超過n，因而f（x）是唯一確定的。

綜上所述，對任意的互不相同的bi（i＝1，2，…，n）及任意的常數(shù)ai（i＝1，2，…，n），存在唯一的次數(shù)小于n的多項式f（x），使得f（bi）＝ai（i＝1，2，…，n）。這就是插值多項式存在性與唯一性定理。

構造多項式 Mi（x）（i＝1，2，…，n），使得它滿足條件：

而：

滿足上述條件。于是得插值多項式為：

這就是n次拉格朗日 （Lagrange）插值多項式。該式表明拉格朗日插值多項式是中國剩余定理的一個特殊形式。

4 算 例

例1 設f（x）被（x－1）、（x－2）、（x－3）除后得到的余式分別為4、8、16，求f（x）被（x－1）（x－2）（x－3）除后的余式。

解 設f（x）＝p（x）（x－1）（x－2）（x－3）＋r（x），其中，r（x）的次數(shù)小于3，從而由已知條件知：r（1）＝f（1）＝4，r（2）＝f（2）＝8，r（3）＝f（3）＝16，由Lagrange插值公式得：

5 結 語

中國剩余定理解決了兩兩互素且每一個同余方程已知的情況下的求解問題，在數(shù)論和近世代數(shù)理論中有重要的應用。筆者給出了中國剩余定理在多項式上的應用，其在其他方面上的應用還有待進一步的研究。

［1］裴定一，徐祥 .信息安全數(shù)學基礎 ［M］.北京：人民郵電出版社，2007：17－18.

［2］藍一中 .高等代數(shù)簡明教程 ［M］.北京：北京大學出版社，2007：136－154.

［3］張禾瑞，郝鈵新 .高等代數(shù) ［M］.北京：高等教育出版社，2007：64.

［4］和斌濤 .K［x］上中國剩余定理的證明和應用 ［J］.科學技術與工程，2010，10（24）：5965－5966.

［5］田金兵，嚴政，劉合國 .關于中國剩余定理 ［J］.湖北大學學報 （自然科學版），2006，28（4）：325－327.