劉合國，趙靜

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

0 引言

中國剩余定理蘊含了一種自然有效的數(shù)學(xué)思想，在理論和應(yīng)用等方面都具有基本性和重要性. 現(xiàn)在，我們要從模的完全剩余系，以及整系數(shù)線性方程組這兩個角度來分別推導(dǎo)這個定理，并給出中國剩余定理的兩種自然解法. 同時我們也給出中國剩余定理在初等數(shù)論、多項式代數(shù)、矩陣代數(shù)等方面的一些應(yīng)用，由此我們可以體會到中國剩余定理在大學(xué)數(shù)學(xué)的基礎(chǔ)課教學(xué)中的重要性.

本研究是文獻(xiàn)[1]的續(xù)篇，涉及的矩陣代數(shù)、數(shù)論等方面的知識見獻(xiàn)[2-4].

1 從完全剩余系的角度出發(fā)

我們從一個簡單的觀察入手.

設(shè)m1,m2,…,mn是n個正整數(shù).對每個整數(shù)0≤a

a=rnm1m2…mn-1+qn,

其中0≤rn

同樣地,qn可唯一地表示為

qn=rn-1m1m2…mn-2+qn-1,

其中0≤rn-1

繼續(xù)下去,a可唯一地表示為

a=r1+r2m1+r3m1m2+…+rnm1m2…mn-1,

其中0≤ri

這樣，我們就證明了下面的定理.

定理1.1設(shè)m1,m2,…,mn是n個正整數(shù),Ri={0,1,…,mi-1}是模mi的完全剩余系.則

r1+r2m1+r3m1m2+…+rnm1m2…mn-1

是模m1m2…mn的完全剩余系，這里ri∈Ri,1≤i≤n.

根據(jù)定理1.1，我們能夠得到中國剩余定理的一種解法.

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

在模m1m2…mn下有唯一解.

定理1.2的證明對n進(jìn)行歸納.當(dāng)n=1時,解是自明的.當(dāng)n=2時,即求解

(1)

因m1與m2互素,故關(guān)于y的同余方程a1+m1y≡a2(modm2)有唯一解y.我們不難驗證x≡a1+m1y(modm1m2)是方程組(1)的解.歸納假設(shè),z是

的解.因m1m2…mn-1與mn互素,故關(guān)于t的同余方程z+tm1m2…mn-1≡an(modmn)有唯一解t.不難驗證x≡z+tm1m2…mn-1(modm1m2…mn)是題中方程組的解.

解的唯一性可以直接驗證,在此略去.

上面的證明給出了求解中國剩余定理的一種方法：依次解出x1,x2,…,xn,使

最后,x≡x1+x2m1+x3m1m2+…+xnm1m2…mn-1(modm1m2…mn)就是所求的解.

下面的例子來自陳志堅編撰的《求一得齋算學(xué)》.

例1.3求解

解依次求解

解得

x1=2,x2=2,x3=1,x4=12.

因此,x=2+3·2+15·1+105·12=1 283.

下面的例子來自黃宗憲《求一術(shù)通解》卷上.

例1.4今有物不知總,以五累減之無剩,以七百一十五累減之剩一十,以二百四十七累減之剩一百四十,以三百九十一累減之剩二百四十五,以一百八十七累減之剩一百零九.問總數(shù)若干?

解用數(shù)學(xué)語言翻譯這一問題,即是求解

該方程組等價于

依次求解

解得

x1=0,x2=3,x3=10,x4=7,x5=0,x6=0.

因此,x=15+5×23×10+5×23×11×7=10 020.

上面的思想可以拓展到域F上的一元多項式的情況.我們可以證明如下的兩個定理.

定理1.5設(shè)m1(x),m2(x),…,mn(x)是域F上的n個非零多項式.F[x]的每個次數(shù)小于?(m1(x)m2(x)…mn(x))的多項式f(x)可唯一地表示為

f(x)=r1(x)+r2(x)m1(x)+r3(x)m1(x)m2(x)+…+rn(x)m1(x)m2(x)…mn-1(x),

其中?(ri(x))

定理1.6(F[x]上的中國剩余定理) 設(shè)m1(x),m2(x),…,mn(x)是F[x]的兩兩互素的多項式.對任意多項式r1(x),r2(x),…,rn(x),存在唯一次數(shù)小于?(m1(x)m2(x)…mn(x))的多項式f(x)，使

f(x)≡ri(x) (modmi(x)),

其中1≤i≤n.

例1.7設(shè)f(x)是2n-1次多項式,其中n是正整數(shù).若f(x)+1被(x-1)n整除，f(x)-1被(x+1)n整除，求f(x).

解注意到恒等式

=(x+1)n·u(x)+(x-1)n·v(x),

所求問題等價于求解

取r1(x)=-1，再求次數(shù)

(-1)+(x-1)n·r2(x)≡1 (mod(x+1)n).

這樣取r2(x)=2v(x)即可.此時，

f(x)=(-1)+(x-1)n·r2(x)

=2(x-1)nv(x)-1

2 從整線性方程組AX=b的角度出發(fā)

在本節(jié)我們將從整線性方程組AX=b的角度來考察中國剩余定理, 由此給出一種矩陣解法.

設(shè)M是n階整數(shù)矩陣. 存在整數(shù)矩陣L, 使得ML=In的充要條件是M的行列式等于±1. 我們把行列式等于±1的矩陣稱為模矩陣. 對任意一個整數(shù)矩陣，進(jìn)行如下的三種初等變換：

1) 互換矩陣的兩行(列),

2) 矩陣的某一行(列)乘以-1,

3) 把矩陣某一行(列)的整數(shù)倍數(shù)加到另一行(列).

我們把這三種初等變換稱為模變換，它們對應(yīng)的初等矩陣都是模矩陣.

按照文獻(xiàn)[4],對于任意的m×n整數(shù)矩陣A,它在模變換下可以變?yōu)槿缦碌臉?biāo)準(zhǔn)形式

其中di(1≤i≤r)是正整數(shù),d1|d2|…|dr.這也意味著,存在m階模矩陣P和n階模矩陣Q，使

稱(d1,d2,…,dr)為A的不變量.

定理2.1整系數(shù)線性方程組AX=b有整數(shù)解的充要條件是系數(shù)矩陣A和增廣矩陣(A,b)具有相同的不變量.

下面我們給出整系數(shù)線性方程組AX=b的一種矩陣解法，同時定理2.1的證明也可從該解法中直接導(dǎo)出.

設(shè)A是m×n矩陣,(d1,d2,…,dr)是A的不變量.則存在m階模矩陣P和n階模矩陣Q,使

于是Ax=b變?yōu)镻-1JQ-1X=b,即J(Q-1X)=Pb.記

由此AX=b進(jìn)一步演變?yōu)橄旅娴暮唵涡问?/p>

(2)

整線性方程組(2)有整數(shù)解當(dāng)且僅當(dāng)cr+1=…=cm=0,且di|ci(1≤i≤r).

(1) 對(A,b)進(jìn)行行的模變換；

Χ可變?yōu)?/p>

AX=b有整數(shù)解當(dāng)且僅當(dāng)cr+1=…=cm=0,di|ci(1≤i≤r),此時系數(shù)矩陣A和增廣矩陣(A,b)具有相同的不變量.當(dāng)AX=b有整數(shù)解時,其解為

其中,yr+1,…,yn是任意整數(shù).

例2.2解整系數(shù)線性方程組

解構(gòu)造矩陣

對X的前3行進(jìn)行行的模變換,前4列進(jìn)行列的模變換,Χ可變?yōu)?/p>

于是方程組的整數(shù)解為

其中k1,k2是任意整數(shù).

再回到中國剩余定理.

定理1.2的另一個證明只需證明解的存在性.明顯地,求解同余方程組

等價于解下面的整線性方程組

(3)

整線性方程組(3)的系數(shù)矩陣為

當(dāng)m1,m2,…,mn兩兩互素時，其在模變換下的標(biāo)準(zhǔn)形為

這樣對任意整數(shù)a1,a2,…,an,整線性方程組(3)的增廣矩陣

的標(biāo)準(zhǔn)形為

顯然A和B具有相同的不變量. 因此，該整線性方程組(3)總有整數(shù)解.

下面的例子即《張邱建算經(jīng)》里著名的“百錢買百雞”問題,該書編寫于公元五世紀(jì).

例2.3今有雞翁一，值錢五；雞母一，值錢三；雞雛三，值錢一. 凡百錢，買百雞，問雞翁、母、雛各幾何?

解用數(shù)學(xué)語言翻譯這個問題.即設(shè)雞翁、母、雛的數(shù)目分別為x,y,z.則

構(gòu)造矩陣

對Χ的前2行進(jìn)行行的模變換，前3列進(jìn)行列的模變換，Χ可變?yōu)?/p>

于是方程組的一般形式解為

因此，所求的解為

3 在數(shù)論里的若干應(yīng)用

例3.1解x3≡ 53 (mod120).

解原方程等價于同余方程組

(4)

根據(jù)Fermat小定理和推廣的Euler定理可得,同余方程組(4)等價于下面的方程組

(5)

按照文獻(xiàn)[1]中的解法，方程組(5)等價于

將第一個方程減去第二個方程再減去第三個方程可得x≡77 (mod120).

例3.2解方程組

解由x2+2x≡3 (mod5),知(x,5)=1.根據(jù)Fermat小定理可得x4≡1 (mod5).這意味著

x2≡1 (mod5)， 或x2≡-1 (mod5).

于是x2+2x≡3 (mod5)等價于

1+2x≡3 (mod5)， 或 -1+2x≡3 (mod5),

即

x≡1 (mod5)， 或x≡2 (mod5).

又

7x≡3 (mod11)等價于21x≡9 (mod11),

即

x≡2(mod11).

這樣原方程等價于

解得x≡46 (mod55)或x≡2 (mod55).

例3.3求x2≡1 (modm)的解的個數(shù).

解設(shè)m=2αp1α1p2α2…psαs是m的標(biāo)準(zhǔn)分解,則x2≡1 (modm)等價于如下的同余方程組

(6)

注意到

x2≡1 (mod2α)等價于下列形式之一：

(ⅰ)x≡1 (mod2α),當(dāng)α=1時;

(ⅱ)x≡±1 (mod2α), 當(dāng)α=2時;

(ⅲ)x≡±1 (mod2α), 或x≡±1 (mod2α-1), 當(dāng)α≥3時.

對每個奇素數(shù)pi,x2≡1 (modpiαi)等價于x≡±1 (modpiαi).

因此，同余方程組(6)等價于

(7)

其中aj∈{±1},0≤j≤s,β=α或α-1.根據(jù)中國剩余定理可得同余方程組(7)存在唯一解.

這樣x2≡1 (modm)的解數(shù)為

其中α≤2,p是奇素數(shù).

例3.4證明：對每個正整數(shù)n,存在n個連續(xù)正整數(shù),其中每個都不能表示為兩個自然數(shù)的平方之和.

例3.4的證明形如4k+3的素數(shù)有無窮多個,現(xiàn)任取n個形如4k+3的素數(shù)p1,p2,…,pn.運用中國剩余定理，下面的同余方程組

有正整數(shù)解x0.

1≡xpi-1≡xpi-3·x2≡ypi-3·(-y2)≡-ypi-1≡-1 (modpi),

矛盾.因此a1,a2,…,an都不能表示為兩個素數(shù)的平方之和.

4 在多項式里的應(yīng)用

例4.1設(shè)f(x)是一個整系數(shù)多項式, 對每個正整數(shù)m, 記

Nm=|{x∈Z|f(x)≡0 (modm)}|，

證明當(dāng)m1,m2,…,ms兩兩互素時，Nm1m2…ms=Nm1·Nm2·…·Nms.

例4.1的證明只需對s=2進(jìn)行證明即可. 記m=m1m2，S={0≤x

Si={0≤x

下證在S與S1×S2之間存在一個自然的一一對應(yīng).

任取x∈S, 即0≤x

反過來, 任取(y1,y2)∈S1×S2, 即m1|f(y1),m2|f(y2).根據(jù)中國剩余定理, 存在唯一的整數(shù)0≤y

因mi|y-yi,y-yi|f(y)-f(yi), 故mi|f(y),m1m2|f(y), 即m|f(y).因此，y∈S.這就證明了

Nm1m2=|S|=|S1×S2|=Nm1·Nm2.

例4.2設(shè)f(x)=(x3+3)(x2+1)(x2+2)(x2-2).證明：對每個正整數(shù)m,f(x)≡0 (modm)恒有解.

例4.2的證明由例4.1可知，我們只需對“m=pn，其中p是素數(shù)”進(jìn)行證明. 對n進(jìn)行歸納.

(1) 當(dāng)p=2時，顯然x0≡1 (mod22)是x3+3≡0 (mod22)的一個根. 我們假設(shè)x1是x3+3≡0 (mod2n)的根，即2a剛好整除x13+3，其中a≥n.記x13+3=2ay1，其中y1是奇數(shù). 由于

(x1+2a)3+3≡x13+3x12·2a+3(mod2a+1)

≡2a(y1+3x12)(mod2a+1)

≡0(mod2a+1)，

則x2=x1+2a是x3+3≡0 (mod2n+1)的根.

歸納假設(shè)x1是x2-t≡0 (modpn)的根. 記x12-t=pnz，其中z是整數(shù). 注意到(x1,p)=1, 則存在整數(shù)s，使2x1s≡1 (modp).

記x2=x1-zspn, 則

x22-t=(x1-zspn)2-t

≡(x12-t)-2x1szpn(modpn+1)

≡pnz-zpn(modpn+1)

≡0(modpn+1).

即x2是x2-t≡0 (modpn+1)的解. 因此, (x2+1)(x2+2)(x2-2)≡0 (modpn)恒有解.

5 在矩陣論中的應(yīng)用

例5.1證明任意n階矩陣A的伴隨矩陣A*可表示為A的多項式.

若A的秩等于n-1,則0是A的特征值,此時存在可逆矩陣P,使得

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

于是

=f(P-1AP).

進(jìn)而

P*A*(P-1)*=P*A*(P*)-1=P-1f(A)P，

A*=(P*)-1P-1f(A)PP*=(PP*)-1f(A)(PP*)=f(A).

綜上可得,n階矩陣A的伴隨矩陣可表示為A的多項式.

設(shè)A是n階矩陣,m是正整數(shù).若矩陣X滿足Xm=A,則稱X是A的m次根.一般情況下,A的m次根不一定存在,即使A的m次根存在,它也不一定能表示為A的多項式.具體參見文獻(xiàn)[5].

例5.2設(shè)n階復(fù)矩陣A滿足rank(A2)=rank(A),m是正整數(shù).則存在矩陣X滿足Xm=A,且X可表示為A的多項式.即此時A存在一個m次根X一定可表示為A的多項式.

其中

這里,ri1≤ri2≤…≤riti=mi.記Jri=λi(Iri+Nri),其中

根據(jù)Taylor公式可得

(8)

其中k是任意正整數(shù)且gk(x)是關(guān)于x的形式冪級數(shù).

容易計算得

其中

因此,X=g(A).

當(dāng)A可逆時,上面的證明思路仍然是適用的.

6 雜題

例6.1設(shè)a、b都是整數(shù).若對任意正整數(shù)n,均有an+n整除bn+n,則a=b.

例6.1的證明假設(shè)a≠b,從條件可以驗證b-a=±1是不可能的.取素數(shù)p不整除b-a.根據(jù)中國剩余定理,存在正整數(shù)n,滿足

若p|a,則p|n,p|an+n.又an+n|bn+n, 則p|bn+n,p|b,進(jìn)而p|b-a.矛盾.因此,p不整除a. 由Fermat小定理可得ap-1≡1 (modp),于是

an+n≡a+n≡0 (modp),

進(jìn)而p|bn+n,注意到p不整除n,p不整除b.再根據(jù)Fermat小定理可得bp-1≡1 (modp),由此可得

bn+n≡b+n≡b-a(modp).

這與p不整除b-a矛盾.

例6.2證明下面關(guān)于x1,x2,x3,x4,u,v,w的方程組

有無窮多組正整數(shù)解.

例6.2的證明記a=12+22+32+42,b=13+23+33+43,c=15+25+35+45.設(shè)x1=axbycz,x2=2axbycz，x3=3axbycz,x4=4axbycz.則方程組變?yōu)?/p>

(9)

要證方程組(9)有無窮多組正整數(shù)解，只需證明下列3個關(guān)于x、y、z的同余方程組都有無窮多正整數(shù)解即可.

解得x=12+30α,y=15+30β,z=10+30γ，其中α、β、γ為自然數(shù). 即原方程組有無窮多組正整數(shù)解.

我們現(xiàn)在考慮如下非常重要的賦值映射.

顯然vp是滿射.

例6.3設(shè)m是正整數(shù),a是整數(shù).證明存在正整數(shù)n，使

v2(n!)≡a(modm).

例6.3的證明設(shè)m=2αl,其中α是自然數(shù),l是奇數(shù).由Euler定理可得2φ(l)≡1 (modl),其中φ(l)是Euler函數(shù). 根據(jù)中國剩余定理,存在正整數(shù)u,滿足

對1≤i≤u,取正整數(shù)ki,記αi=kiφ(l)+1,使得

α<α1<α2<…<αu,

此時

2αi-1=2kiφ(l)+1-1=2·(2φ(l))ki-1≡1 (modl)，

現(xiàn)記n=2α1+2α2+…+2αu,可以驗證

v2(n!)=n-u

=(2α1-1)+(2α2-1)+…+(2αn-1)

≡u≡a(modl),

v2(n!)=n-u≡-u≡a(mod2α).

因此,v2(n!)≡a(modm).

例6.4設(shè)p1,p2,…,pn是兩兩互異的素數(shù),a1,a2,…,an均是整數(shù).若ε>0,則存在整數(shù)x,使得|x-ai|pi<ε,其中1≤i≤n.

證取充分大的整數(shù)e1,e2,…,en使pi-ei<ε,其中i=1,2,…,n.根據(jù)中國剩余定理,存在整數(shù)x,滿足

此時piei|x-ai,從而|x-ai|pi≤pi-ei<ε.