數(shù)學(xué)基礎(chǔ)課里的中國剩余定理和Lagrange插值公式

劉合國，徐行忠，廖軍

(湖北大學(xué)數(shù)學(xué)與統(tǒng)計學(xué)學(xué)院， 湖北 武漢 430062)

中國剩余定理在數(shù)學(xué)里起著重要的作用，是中國先賢智慧的結(jié)晶．該定理從數(shù)系的基本運算律出發(fā)，用最典型的“線性”方法解決問題，這種思想是極其深刻的．這些年來，我們在從事高等代數(shù)、初等數(shù)論、近世代數(shù)、代數(shù)學(xué)等課程的教學(xué)過程中，積累了對這個定理的認(rèn)識，它們對理解這個定理是有作用的．現(xiàn)不揣淺陋，撰寫成文，望同好者批評指正．

本文中采用的術(shù)語和符號都是標(biāo)準(zhǔn)的，按照文獻[1-3]．

1 四首歌訣

《孫子算經(jīng)》是中國古代的一部數(shù)學(xué)名著，成書于公元三世紀(jì)至五世紀(jì)左右，其卷下之26題，即是歷史上有名的“物不知數(shù)”：

今有物，不知其數(shù)，三三數(shù)之剩二，五五數(shù)之剩三，七七數(shù)之剩二，問物幾何？

《孫子算經(jīng)》不僅給出了正確答案，而且給出了完美的解法：

答曰：二十三．

術(shù)曰：三三數(shù)之剩二，置一百四十；五五數(shù)之剩三，置六十三；七七數(shù)之剩二，置三十．并之，得二百三十三，以二百一十減之，即得．

凡三三數(shù)之剩一，則置七十；五五數(shù)之剩一，則置二十一；七七數(shù)之剩一，則置十五．一百六以上，以一百五減之，即得．

用現(xiàn)代語言重現(xiàn)這個解法，即同余方程組

的答案為: 140+63+30=233,233-210=23.

一般地，求解同余方程組

的幾個關(guān)鍵數(shù)字是 70，21，15和105，答案為r：

70a+21b+15c=105q+r,1≤r≤105.

這個解法是非常奇特的！初看起來，它是迂回的，不是單刀直入的，但它抓住了問題的本質(zhì)，找到了最關(guān)鍵的節(jié)點，通過線性組合得到答案．這是絕頂?shù)闹腔?！南宋淳熙十五?1188)，大型類書《錦繡萬花谷》問世，其前集卷三十八記載了一首“易數(shù)詩”：

三人同行七十稀，五郎念一鎮(zhèn)相隨，

七哥記取常十五，此是易數(shù)大希夷．

這里“念”是“廿”的大寫，代表二十，詩里明白地點出了三個最關(guān)鍵的數(shù)字：70，21，15．面對虛寂玄妙的解答，古人發(fā)出了“易數(shù)希夷”的感嘆．

在中國古代數(shù)學(xué)家里，秦九韶對中國剩余定理做出了決定性的貢獻．秦九韶(1208—1261)，字道古，生于普州安岳(今四川省安岳縣)，在南宋淳祐七年(1247)完成了不朽著作《數(shù)書九章》，它是中國古代最重要的數(shù)學(xué)著作之一．科學(xué)史家George Sarton在所著《Introduction to the history of science》之卷II．2里高度評價秦九韶：

One of the greatest mathematicians of his race，of his time，and indeed of all times．

在《數(shù)書九章》里，秦九韶創(chuàng)造性地發(fā)明了大衍求一術(shù)，即給出了解同余方程ax≡1(modm)的一般算法，這是求解中國剩余定理的決定性步驟．

有宋一代，華夏文明昌盛，道學(xué)繁榮．秦九韶對他的數(shù)學(xué)成就是非常自豪的，《數(shù)書九章》序說：

(數(shù))大則可以通神明，順性命；小則可以經(jīng)世務(wù)，類萬物．要其歸，則數(shù)與道非二本也．

秦九韶將數(shù)學(xué)提升到“道”的高度．清代揚州學(xué)派的代表人物之一，“揚州通儒”焦循(1763—1820)在《天元一釋》卷下高度評價秦九韶的歷史功績：

大衍之術(shù)，即《孫子算經(jīng)》三三五五七七之術(shù)也．此術(shù)《九章》所無，而見于《孫子》．今則歸入孺子，或以為戲．《孫子》雖詳其術(shù)，而秦氏則闡其微而暢發(fā)之．其三三置七十，即大衍求一術(shù)也．

中國剩余定理玄妙高遠(yuǎn)， 不斷被編成歌訣進入小說筆記， 這個現(xiàn)象是十分罕見的．

周密(1232—1298)，字公瑾，生于杭州，工詩詞，擅書畫，是南宋筆記大家，著述甚豐，所著《志雅堂雜鈔》卷九之“陰陽算術(shù)”記載了一首解答“物不知數(shù)”的歌訣:

三歲孩兒七十稀， 五留廿一事尤奇，

七度上元重相會， 寒食清明便可知．

前兩句蘊含了兩個數(shù)字：70和21．上元節(jié)就是元宵節(jié)，借指正月十五，這樣第三句蘊含了數(shù)字“15”．第四句蘊含了數(shù)字“105”，需要做點說明：在中國古代的很長時間里，把冬至當(dāng)作新年的開始，冬至距寒食清明節(jié)多在105天．這樣解“物不知數(shù)”的關(guān)鍵數(shù)字：70，21，15和105都在歌訣里出現(xiàn)了．

褚人獲(1635—1682)，字稼軒，江蘇長州人．未中試，多才多藝，著有《隋唐演義》，《堅瓠集》等．其《堅瓠集》戊集卷一之“隔壁笑”記載了一首歌訣:

三人逢零七十稀，五馬沿盤廿一奇(一作五人折桂廿一枝)，

七星約在元宵里，一百零五定為除．

顯然，這首歌訣同樣寫下了解“物不知數(shù)”的四個關(guān)鍵數(shù)字：70，21，15和105．

程大位(1533—1606)，字汝思，安徽休寧人．他在經(jīng)商過程中，積累了豐富的數(shù)學(xué)問題及其解法，編撰了《直指算法統(tǒng)宗》，強調(diào)指出數(shù)學(xué)在國計民生中的重要性，其《書直指算法統(tǒng)宗后》寫道：

數(shù)居六藝之一，其來尚矣，蓋自虙戲宰世，龍馬負(fù)圖，而數(shù)肇端．軒后紀(jì)歷，隸首作算，而法始衍．故圣人繼天立極，所以齊度量而立民信者，不外黃鐘九寸之管，所以定四時而成歲功者，不外周天三百六十五度之?dāng)?shù)．以至遠(yuǎn)而天地之高廣，近而山川之浩衍，大而朝廷軍國之需，小而民生日用之費，皆莫能外．?dāng)?shù)詎不重己哉？

程大位在書里把不少問題的解法用歌訣的形式呈現(xiàn)出來．特別地，他在卷五里將“物不知總”的解法寫成了通俗易懂、廣為傳頌的“孫子歌”：

三人同行七十稀，五樹梅花廿一枝，

七子團圓正半月，除百零五便得知．

“物不知數(shù)”及其解法的影響超出了數(shù)學(xué)之外，例如金庸在他的成名之作《射雕英雄傳》里，就引述了“物不知數(shù)”和程大位的歌訣，用來加強其行文的份量．當(dāng)然，這屬于“誤引”，因《射雕英雄傳》講述的是南宋故事，那時程大位的歌訣還未問世．中國剩余定理對中國文化的影響于此也可見一斑．

2 歌訣的意義

在這節(jié)我們要研究為什么70，21，15和105就是求解“物不知數(shù)”的關(guān)鍵．105=3×5×7,105的來歷是一目了然的，容易看到

粗略地說，70，21，15就是求解同余方程組

(1)

的“基底”，a,b,c只是解的“坐標(biāo)”．方程組 (1)的解為

x≡a·70+b·21+c·15(mod105).

按照中國古代傳統(tǒng)，取x為最小正整數(shù)當(dāng)作方程組(1)的解．

為了理解上面“基底”的準(zhǔn)確意義，我們引進一個概念．

設(shè)R是含幺交換環(huán)，RM是R上的模．如果X是M的非零元組成的子集，滿足

1)M的任意元m可表示為m=r1x1+r2x2+…+ruxu,ri∈R,xi∈X,即M=∑x∈XRx.

2)若s1y1+s2y2+…+svyv=0,其中si∈R,yi∈X, 則s1y1=s2y2=…=svyv=0.

那么我們稱X是M的一組基底．

順便提一下，含幺環(huán)里單位元的正交冪等元之分解是研究環(huán)結(jié)構(gòu)的重要工具．

例1解方程x3-3x+5≡0 (mod105).

解：方程化為

化簡(2a)式，由Fermat小定理，x3≡x(mod3),得

x≡1(mod3)

(3)

化簡(2b)式，x(x2-3)≡0(mod5),因5x2-3, 故

x≡0(mod5)

(4)

化簡(2c)式，由Fermat小定理，x6≡1(mod7),故x3≡±1(mod7),代入(2c)式，得3x≡5±1(mod7),所以

x≡2(mod7)或x≡6(mod7)

(5)

運用歌訣解得x≡100(mod105)或x≡55(mod105).

3 中國剩余定理

理解了前一節(jié)里70，21，15在求解“物不知數(shù)”的意義，我們就可以自然地推出一般形式的中國剩余定理，其中的關(guān)鍵一步是秦九韶的“大衍求一術(shù)”．

定理3.1(中國剩余定理) 設(shè)m1,m2,…,mn是兩兩互素的正整數(shù)，對任意整數(shù)a1,a2,…,an,下列方程組

在模m1m2…mn下有唯一解．

定理3.1的證明對任意的1≤i≤n, 設(shè)xi滿足同余方程組

xi≡δij(modmj),1≤j≤n.

其中δij是Kronecker符號，xi≡1(modmi)等價于xi+uimi=1;對所有的j≠i,xi≡0(modmj)等價于xi=vi∏j≠imj.即有

因(mi,∏j≠imj)=1,據(jù)大衍求一術(shù)，可得ui,vi,進而得到xi.

記x=a1x1+a2x2+…+anxn,容易驗證x即是解．

下證唯一性．設(shè)a,b是方程組的兩個解，則有

則a≡b(modmi)對任意的1≤i≤n成立，于是a≡b(modm1m2…mn).

uimi+viMi=1.

取xi=viMi.將上述前n-1個式子相乘得到

另一方面，容易驗證如下的事實．

中國剩余定理是解決存在性問題的有力工具．

例2證明對任意正整數(shù)n,均存在n個連續(xù)整數(shù)，它們都有一個平方因子．

證明選取n個互異素數(shù)p1,p2,…,pn,考慮下面的同余方程組

例3證明對任意正整數(shù)n,存在整數(shù)a和b,使對任意的1≤r,s≤n,都有(a+r,b+s)>1.

證明選取n2個互異素數(shù)pij,1≤i,j≤n.設(shè)a是同余方程組

的解，b是同余方程組

的解．對任意的1≤r,s≤n,有prs∣(a+r,b+s),從而(a+r,b+s)>1.

4 單刀直入的解法

在上一節(jié)求解線性同余方程組時，我們采用的方法是間接地找到所需的“基底”，再通過線性組合得到問題的答案，這與我們之前求解線性方程組的思路具有很大不同．接下來，我們借用解線性方程組的理念來處理中國剩余定理的求解問題，其出發(fā)點是下面兩條：

(i) 設(shè)k,m是正整數(shù)，a,b是整數(shù)，則

a≡b(modm)?m∣(a-b)

?km∣(ka-kb)

?ka≡kb(modkm)

(ii) 中國剩余定理．

下面設(shè)m1,m2,…,mn是兩兩互素的正整數(shù)，對任意整數(shù)a1,a2,…,an,求解同余方程組

(6)

為了進行線性運算，我們需要把模統(tǒng)一化，記M=m1m2…mn,Mi=M/mi.則上面的方程組(6)式等價于下面的方程組(7)式．

(7)

因(M1,M2,…,Mn)=1,故存在整數(shù)k1,k2,…,kn, 使k1M1+k2M2+…+knMn=1.于是x≡k1M1a1+k2M2a2+…+knMnan(modM).根據(jù)中國剩余定理里解的唯一性，x即為所求．

上面的步驟可以用兩句話來概括．

(iii) 統(tǒng)一模，即把方程組(6)式化為方程組(7)式．

(iv) 湊“1”，即由方程組(7)里x的系數(shù)M1,M2,…,Mn經(jīng)過整數(shù)線性組合湊出“1”即可．

下面舉例說明．

例4(韓信點兵) 相傳劉邦拜韓信為大將后，某天來到韓信的練兵場，見有約二千名士兵正在操練．期間韓信告訴劉邦，他并不知道練兵場上到底有多少士兵，但如果命令士兵們先后以七人一組，十一人一組，十三人一組集結(jié)成小組，并把每次余下不能組成七人(或十一人，或十三人)的人數(shù)報給他，他就可以知道士兵的準(zhǔn)確人數(shù)．劉邦很驚訝，就按照韓信的要求做了一番操作，報給韓信三個數(shù)字：3，4，8．韓信很快就告訴劉邦，士兵數(shù)目是1 984．劉邦驗證答案后，非常信服，確信韓信具有非凡的才能．

用數(shù)學(xué)語言翻譯這個故事，即是求解

(8)

其中x在2 000左右．如果這個故事是真實的，那么在劉邦到來之前韓信肯定知道幾個關(guān)鍵的數(shù)字：715， 364，924和7×11×13=1 001,韓信根據(jù)報給他的3個數(shù)：3，4，8，即可進行計算：

3×715+4×364+8×924=10 993,10 993-9×1 001=1 984,

1984就是士兵數(shù)目． 現(xiàn)在我們用本節(jié)的方法再來求解一次．

解： 同余方程組(8)等價于

(9b)-(9c)得

14x≡-252(mod1 001)

(10)

(9a)-(10)×10得

3x≡429+2 520≡2 949≡-54(mod1 001)

(11)

(9b)-(11)×30得

x≡364+54×30=1 984(mod1 001).

故操練的士兵數(shù)為1984．

我們可以把本節(jié)的方法推廣到一般情形．

定理4.1設(shè)m1,m2,…,mn都是正整數(shù)，則同余方程組

有解的充要條件是對1≤i,j≤n,均有(mi,mj)∣(bi-bj).

當(dāng)方程組有解時，記M=[m1,m2,…,mn],Mi=M/mi,則存在整數(shù)k1,k2,…,kn使得k1M1+k2M2+…+knMn=1,方程組的解為

x≡k1M1b1+k2M2b2+…+knMnbn(modM).

例5解同余方程組

解． 容易驗證(mi,mj)∣(bi-bj), 因此方程組有解．由于[6,9,15]=90, 原方程組等價于

將第二個方程加上第三個方程減去第一個方程得到x≡67(mod90).

5 從中國剩余定理到Lagrange插值公式

設(shè)F是一個域，F(xiàn)上的多項式環(huán)F[x]和整數(shù)環(huán)Z是最常見的兩個Euclid環(huán)．我們可以把前面的中國剩余定理推廣到F[x]. 為方便計，先引進一個符號．

設(shè)m(x)是F[x]的非常數(shù)多項式，f(x),g(x)∈F[x],若m(x)整除f(x)-g(x), 則記為f(x)≡g(x)(modm(x)).這與Z上的同余符號具有類似的性質(zhì)：

設(shè)f1(x)≡g1(x)(modm(x)),f2(x)≡g2(x)(modm(x)),k(x)∈F[x],則k(x)f1(x)+f2(x)≡k(x)g1(x)+g2(x)(modm(x)).

f(x)≡ri(x)(modmi(x)),1≤i≤n.

定理5.1的證明完全類似中國剩余定理的證明過程求f1(x),f2(x),…,fn(x).對任意的1≤i≤n,由于(mi(x),∏j≠imj(x))=1,則存在多項式ui(x),vi(x),使得ui(x)mi(x)+vi(x)∏j≠imj(x)=1.取fi(x)=vi(x)∏j≠imj(x).則fi(x)滿足

fi(x)≡δij(modmj(x)),1≤j≤n.

記

g(x)=r1(x)f1(x)+r2(x)f2(x)+…+rn(x)fn(x)

=q(x)m1(x)m2(x)…mn(x)+r(x).

則r(x)即為所求方程組的解．

下證解的唯一性．設(shè)a(x),b(x)都是滿足定理中方程組的解， 即

a(x)≡ri(x)(modmi(x)),1≤i≤n，

b(x)≡ri(x)(modmi(x)),1≤i≤n.

ui(x)mi(x)+vi(x)Mi(x)=1.

將上述n-1個式子相乘得到

對任意g(x)∈F[x],g(x)=u1(x)f1(x)+u2(x)f2(x)+…+un(x)fn(x).于是

另一方面，在R上，我們?nèi)菀昨炞C下面的關(guān)系式:

接下來我們考慮定理的最極端情況．設(shè)a1,a2,…,an是F上的n個兩兩互異的元素， 此時m1(x)=x-a1,m2(x)=x-a2,…,mn(x)=x-an是F[x]的兩兩互素的多項式．根據(jù)上述定理，對F上的任意n個元素b1,b2,…,bn, 存在唯一的次數(shù)小于n的多項式f(x), 使得對每個1≤i≤n, 有

f(x)≡bi(modx-ai),

即存在qi(x)∈F[x], 使f(x)=qi(x)(x-ai)+bi,這等價于f(ai)=bi,這樣我們就得到了

定理5.2(Lagrange插值定理) 設(shè)a1,a2,…,an是F的n個兩兩互異的元素，則對F的任意n個元素b1,b2,…,bn,存在唯一次數(shù)

遵循中國剩余定理的思路，我們能夠程序化地求出L(x)．

對每個1≤i≤n, 求次數(shù)小于n的多項式Li(x), 使

Li(aj)=δij,1≤j≤n.

容易看出

這樣L(x)=b1L1(x)+b2L2(x)+…+bnLn(x).

L1(x),L2(x),…,Ln(x)是域F上的次數(shù)小于n的多項式構(gòu)成的n維線性空間F[x]n的一組基底．事實上，L1(x),L2(x),…,Ln(x)線性無關(guān)．若k1L1(x)+k2L2(x)+…+knLn(x)=0,ki∈F,分別以x=a1,a2,…,an代入，則得k1=k2=…=kn=0.

又dimFF[x]n=n. 因此L1(x),L2(x),…,Ln(x)是線性空間F[x]n的一組基底．

(iii)L1(x)+L2(x)+…+Ln(x)=1.

6 另兩種線性代數(shù)推導(dǎo)

上節(jié)從中國剩余定理出發(fā)，導(dǎo)出Lagrange插值公式， 這個過程也是迂回的．由于本研究主要是從線性方法入手，下面給出Lagrange插值公式的另外兩個線性代數(shù)證明．

證法一對F上的n個兩兩互異的元素a1,a2,…,an,以及F上的任意n個元素b1,b2,…,bn. 關(guān)于未知數(shù)x0,x1,…,xn-1的線性方程組

的系數(shù)行列式是a1,a2,…,an的Vandermonde行列式，它顯然不等于0，故該線性方程組有且僅有一組解(x0,x1,…,xn-1),于是多項式L(x)=x0+x1x+x2x2+…+xn-1xn-1即為所求．

下面我們來求出這個多項式的顯式表達．方程組的系數(shù)行列式為

根據(jù)Cramer法則，

其中Δk,i+1是Δ的第k行第i+1列元素的代數(shù)余子式，于是

L(x)=x0+x1x+x2x2+…+xn-1xn-1

證法二考慮下面的函數(shù)方程

則L(x)為所求的多項式當(dāng)且僅當(dāng)L(x)滿足上述方程．事實上，按第一行展開左邊的行列式，即知L(x)是F上次數(shù)小于n的多項式．當(dāng)L(x)滿足上述方程時，對每個1≤i≤n,有

則有

必須L(ai)-bi=0,即L(ai)=bi.

再按最后一列展開函數(shù)方程中的行列式，化簡得到

7 應(yīng)用

在處理多項式的存在性問題時，中國剩余定理和Lagrange插值公式是兩個合適的工具．

例6證明對任意的n階復(fù)矩陣A, 存在多項式s(λ),n(λ),使得A=s(A)+n(A), 并且s(A)是可對角化矩陣，n(A)是冪零矩陣．

證明設(shè)A的特征值為λ1,λ2,…,λr,A的極小多項式為

設(shè)Ui為λi的根子空間，即

Ui={α∈Cn∣(A-λiE)miα=0},

根據(jù)中國剩余定理，存在多項式s(λ),使得

我們斷言s(A)是可對角化矩陣，A-s(A)是冪零矩陣．事實上，對每個1≤i≤r,從s(λ)≡λi(mod(λ-λi)mi),知存在fi(λ),使得s(λ)=λi+fi(λ)(λ-λi)mi.則有s(A)=λiE+fi(A)(A-λiE)mi.因此s(A)純量地作用在Ui上，即有s(A)αij=λiαij,1≤j≤ni.于是s(A)有n個線性無關(guān)的特征向量，從而是可以對角化的．

例7設(shè)n階矩陣A有n個互異的特征值，AB=BA. 證明B=f(A),對某個多項式f(x)∈F[x]成立．

證明由于n階矩陣A有n個互異的特征值，則存在n階可逆矩陣P,使得

由條件有AB=BA,故P-1APP-1BP=P-1BPP-1AP.注意到對i≠j,我們有λi≠λj,則可得P-1BP為對角矩陣．設(shè)

則由Lagrange插值公式，存在唯一次數(shù)小于n的多項式f(x), 使得f(λi)=μi,對所有的1≤i≤n成立．

因此P-1BP=f(P-1AP),從而得B=f(A).

8 一般性結(jié)論

前面涉及的中國剩余定理及其證明對一般的含幺環(huán)也是成立的，我們從文獻[3]中摘錄下面的兩個定理，略去它們的證明．

定理8.1(中國剩余定理) 設(shè)含幺環(huán)R的理想I1,I2,…,In兩兩互素，則對R的任意元素a1,a2,…,an,

在模I1∩I2∩…∩In下有唯一解．

定理8.2設(shè)含幺環(huán)R的理想I1,I2,…,In兩兩互素，則有環(huán)同構(gòu)

R/I1∩I2∩…∩In?R/I1⊕R/I2…⊕R/In.

曾有專家認(rèn)為，下面的群論結(jié)果也屬于中國剩余定理．

設(shè)G是一個群，M和N都是G的正規(guī)子群，G=MN, 則

G/M∩N?G/M×G/N.

我們是不能認(rèn)同這個觀點的．中國剩余定理是非常自然的插值工具，是數(shù)系運算之基本法則的絕佳體現(xiàn)，是線性方法的深刻應(yīng)用．除了在形式上與定理8.2的最簡單情況相似外，這個群論結(jié)果與中國剩余定理的內(nèi)涵是沒有什么關(guān)聯(lián)的．