劉合國(guó)，趙靜

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

0 引言

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

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

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

我們從一個(gè)簡(jiǎn)單的觀察入手.

設(shè)m1,m2,…,mn是n個(gè)正整數(shù).對(duì)每個(gè)整數(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個(gè)正整數(shù),Ri={0,1,…,mi-1}是模mi的完全剩余系.則

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

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

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

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

在模m1m2…mn下有唯一解.

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

(1)

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

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

解的唯一性可以直接驗(yàn)證,在此略去.

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

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

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

例1.3求解

解依次求解

解得

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

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

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

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

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

該方程組等價(jià)于

依次求解

解得

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

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

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

定理1.5設(shè)m1(x),m2(x),…,mn(x)是域F上的n個(gè)非零多項(xiàng)式.F[x]的每個(gè)次數(shù)小于?(m1(x)m2(x)…mn(x))的多項(xiàng)式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]上的中國(guó)剩余定理) 設(shè)m1(x),m2(x),…,mn(x)是F[x]的兩兩互素的多項(xiàng)式.對(duì)任意多項(xiàng)式r1(x),r2(x),…,rn(x),存在唯一次數(shù)小于?(m1(x)m2(x)…mn(x))的多項(xiàng)式f(x)，使

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

其中1≤i≤n.

例1.7設(shè)f(x)是2n-1次多項(xiàng)式,其中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),

所求問(wèn)題等價(jià)于求解

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

下面我們給出整系數(shù)線(xiàn)性方程組AX=b的一種矩陣解法，同時(shí)定理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)橄旅娴暮?jiǎn)單形式

(2)

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

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

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

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

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

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

解構(gòu)造矩陣

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

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

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

再回到中國(guó)剩余定理.

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

等價(jià)于解下面的整線(xiàn)性方程組

(3)

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

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

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

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

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

下面的例子即《張邱建算經(jīng)》里著名的“百錢(qián)買(mǎi)百雞”問(wèn)題,該書(shū)編寫(xiě)于公元五世紀(jì).

例2.3今有雞翁一，值錢(qián)五；雞母一，值錢(qián)三；雞雛三，值錢(qián)一. 凡百錢(qián)，買(mǎi)百雞，問(wèn)雞翁、母、雛各幾何?

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

構(gòu)造矩陣

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

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

因此，所求的解為

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

例3.1解x3≡ 53 (mod120).

解原方程等價(jià)于同余方程組

(4)

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

(5)

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

將第一個(gè)方程減去第二個(gè)方程再減去第三個(gè)方程可得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)等價(jià)于

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

即

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

又

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

即

x≡2(mod11).

這樣原方程等價(jià)于

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

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

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

(6)

注意到

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

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

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

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

對(duì)每個(gè)奇素?cái)?shù)pi,x2≡1 (modpiαi)等價(jià)于x≡±1 (modpiαi).

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

(7)

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

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

其中α≤2,p是奇素?cái)?shù).

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

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

有正整數(shù)解x0.

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

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

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

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

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

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

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

Si={0≤x

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

任取x∈S, 即0≤x

反過(guò)來(lái), 任取(y1,y2)∈S1×S2, 即m1|f(y1),m2|f(y2).根據(jù)中國(guó)剩余定理, 存在唯一的整數(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).證明：對(duì)每個(gè)正整數(shù)m,f(x)≡0 (modm)恒有解.

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

(1) 當(dāng)p=2時(shí)，顯然x0≡1 (mod22)是x3+3≡0 (mod22)的一個(gè)根. 我們假設(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的多項(xiàng)式.

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

根據(jù)中國(guó)剩余定理可得,存在多項(xiàng)式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的多項(xiàng)式.

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

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

其中

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

根據(jù)Taylor公式可得

(8)

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

容易計(jì)算得

其中

因此,X=g(A).

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

6 雜題

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

例6.1的證明假設(shè)a≠b,從條件可以驗(yàn)證b-a=±1是不可能的.取素?cái)?shù)p不整除b-a.根據(jù)中國(guó)剩余定理,存在正整數(shù)n,滿(mǎ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的方程組

有無(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)有無(wú)窮多組正整數(shù)解，只需證明下列3個(gè)關(guān)于x、y、z的同余方程組都有無(wú)窮多正整數(shù)解即可.

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

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

顯然vp是滿(mǎn)射.

例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ù)中國(guó)剩余定理,存在正整數(shù)u,滿(mǎn)足

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

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

此時(shí)

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

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

v2(n!)=n-u

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

≡u(píng)≡a(modl),

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

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

例6.4設(shè)p1,p2,…,pn是兩兩互異的素?cái)?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ù)中國(guó)剩余定理,存在整數(shù)x,滿(mǎn)足

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