中國剩余定理與插值多項(xiàng)式關(guān)系的探究

黃湧輝

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

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

1 n次拉格朗日 （Lagrange）插值多項(xiàng)式

對(duì)于n＋1個(gè)互不相同的插值節(jié)點(diǎn)xi，i＝0，1，2，…，n，由n次插值多項(xiàng)式的惟一性，可對(duì)每個(gè)插值節(jié)點(diǎn)xi作出相應(yīng)的n次插值基函數(shù)li（x），i＝0，1，2，…，n。要求x0，x1，…，xi－1，xi＋1，…，xn是li（x）的零點(diǎn)，因此可設(shè)：

因而有：

作其組合：

那么Ln（x）不高于n次且滿足Ln（xi）＝f（xi），i＝0，1，2，…，n，故Ln（x）是關(guān)于插值點(diǎn)x0，x1，…，xn的插值多項(xiàng)式，這種插值形式稱為n次拉格朗日 （Lagrange）插值多項(xiàng)式。

2 中國剩余定理

定理1 （中國剩余定理［1］） 設(shè)m1，m2，…，mn是兩兩互素的自然數(shù)，令：

則方程組：

的解為：

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

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

由中國剩余定理可得到如下結(jié)論：

定理2 設(shè)m1（x），m2（x），…，mn（x）是n個(gè)兩兩互素的且次數(shù)n≥1多項(xiàng)式，任給n個(gè)多項(xiàng)式a1（x），a2（x），…，an（x），則一定存在多項(xiàng)式f（x），使得：

并且f（x）關(guān)于m（x）是唯一確定，其中m（x）＝m1（x）m2（x）…mn（x）。

證明 先對(duì)方程組中的式（1）和式（2）進(jìn)行討論。由于m1（x）和m2（x）互素，所以利用輾轉(zhuǎn)相除法找到p（x）和q（x），使得p（x）m1（x）＋q（x）m2（x）＝1。兩邊同時(shí)乘以a1（x）－a2（x）得：

即：

也即：

故：

由此可得：

故：

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

3 關(guān)系探究

記mi（x）＝x－bi∈Q［x］，i＝1，2，…，n，其中，bi是互不相等的常數(shù)。由于mi（x），（i＝1，2，…，n）為有理數(shù)域Q［x］上的不可約多項(xiàng)式，從而mi（x）是兩兩互素的多項(xiàng)式。由于mi（x）≡mi（bi）（mod（x－bi）），（i＝1，2，…，n），由中國剩余定理知，一定存在多項(xiàng)式f（x），使得：

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

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

構(gòu)造多項(xiàng)式 Mi（x）（i＝1，2，…，n），使得它滿足條件：

而：

滿足上述條件。于是得插值多項(xiàng)式為：

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

4 算 例

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

解 設(shè)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 結(jié) 語

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

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

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

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

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

［5］田金兵，嚴(yán)政，劉合國 .關(guān)于中國剩余定理 ［J］.湖北大學(xué)學(xué)報(bào) （自然科學(xué)版），2006，28（4）：325－327.