石文章 劉合國

(1.湖北大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)學(xué)院,武漢,430062?2.海南大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,海口,570228)

1 引言

中國剩余定理是中國古代數(shù)學(xué)的一項(xiàng)光輝成就,它是線性同余方程組理論的一個(gè)核心內(nèi)容,也是數(shù)論的一條基本原理.我們知道,一個(gè)整系數(shù)方程ax=b有解,當(dāng)且僅當(dāng)對(duì)任意的正整數(shù)m,同余方程ax≡b(modm)有解.引入同余的概念后,利用同余的理論和思想,可以大大簡化數(shù)論中的相關(guān)問題.關(guān)于線性同余方程組理論的研究已有頗多成果,參見文獻(xiàn)[1,5,6].文獻(xiàn)[2]利用整數(shù)矩陣的初等變換證明了中國剩余定理,并提供了一個(gè)求解的途徑.文獻(xiàn)[1]第二章給出了多元一次同余方程有解的充要條件,并在有解時(shí)給出了解的個(gè)數(shù).

本文將從整數(shù)矩陣的模變換出發(fā),研究在一般條件下,

的求解問題.利用矩陣的不變因子給出多元一次同余方程組Ax≡b(modm)有解的一個(gè)充要條件,進(jìn)而給出該同余方程組在有解情況下解的個(gè)數(shù),由此自然地得到?；ニ氐亩嘣淮瓮喾匠探M有解的充要條件及解的個(gè)數(shù).

本文采用文獻(xiàn)[1,5,6]的標(biāo)準(zhǔn)符號(hào).

2 預(yù)備知識(shí)

設(shè)A是n階整數(shù)矩陣.若A的行列式等于+1 或-1,則稱A為模矩陣.對(duì)于任一整數(shù)矩陣,它有如下三種初等變換:

(1) 交換矩陣的兩行(列)?

(2) 將矩陣的某一行(列)乘上-1?

(3) 把矩陣某一行(列)的整數(shù)倍數(shù)加到另一行(列).易知,這三種初等變換對(duì)應(yīng)的初等矩陣均為模矩陣.

定義2.1([1]) 對(duì)矩陣Am×n,Bm×n,若存在兩個(gè)模方陣Um×m,Vn×n使得

則稱A與B相似,記為A～B.

定理2.1([1]) 任一整數(shù)矩陣Am×n必與一形如

的矩陣相似,其中di是正整數(shù),且di|di+1,i=1,···,r-1.

定義2.2([1]) 若矩陣A與形如(2.1)的矩陣相似,則稱(2.1)為矩陣A的相似標(biāo)準(zhǔn)形,并且稱d1,d2,···,dr為A的不變因子.

定理2.2([1]) 任一模方陣經(jīng)過一系列初等變換后,可變成單位陣.

定理2.1 又可表述成:經(jīng)一系列初等變換,可將一矩陣變成相似標(biāo)準(zhǔn)形的形式.因?yàn)槌醯茸儞Q不改變矩陣的i級(jí)子行列式的最大公因數(shù),因此可得下述定理:

定理2.3([1]) 若A～B,則A內(nèi)所有i級(jí)子行列式的最大公因數(shù)與B內(nèi)所有i級(jí)子行列式的最大公因數(shù)相等.

結(jié)合(2.1)的相似標(biāo)準(zhǔn)形,可知

即為Am×n的i級(jí)子行列式的最大公因數(shù).

定理2.4([1]) 任一矩陣的相似標(biāo)準(zhǔn)形是唯一的.

接下來的定理是我們判定整線性方程組有解的一個(gè)重要工具,其證明方法也是本文解決同余方程組問題的一個(gè)關(guān)鍵技巧.

定理2.5([2]) 整線性方程組Ax=b有整數(shù)解當(dāng)且僅當(dāng)其系數(shù)矩陣與增廣矩陣有相同的不變因子.

證明設(shè)A是m×n階矩陣,J是A的相似標(biāo)準(zhǔn)形,則存在m階模矩陣U和n階模矩陣V,使得

于是由Ax=b,可得(U-1JV-1)x=b,即J（V-1x）=Ub.記

則Ax=b有解等價(jià)于下列方程

有解.故整線性方程組Ax=b有整數(shù)解的充要條件為

由上可知

若(2.4)成立,則由(2.5)可得

反之,若(2.6)成立,則有

考慮矩陣

由兩相似矩陣的所有i級(jí)子行列式的最大公因數(shù)相等,可得:當(dāng) 1≤i≤r時(shí),

即(2.4)成立.

證畢.

推論2.1 整線性方程組Ax=b有整數(shù)解當(dāng)且僅當(dāng)矩陣與增廣矩陣的所有的i級(jí)子行列式的最大公因數(shù)相等.

3 兩種角度下的一類一元一次同余方程組

定理3.1 (中國剩余定理)設(shè)m1,m2,···,mn是兩兩互素的正整數(shù).則對(duì)任意的整數(shù)a1,a2,···,an,下面的同余方程組

在模m1m2···mn下有唯一解.

文獻(xiàn)[2]分別從完全剩余系和整線性方程組這兩個(gè)角度出發(fā)給出了中國剩余定理的證明,并提供了矩陣求解的方法,這也是本文解決問題的一大路徑.接下來的定理,我們將分別從這兩種角度給出證明.

定理3.2 設(shè)m1,m2,···,mn都是正整數(shù)? 記dij=(mi,mj),其中1≤i

有解的充要條件是dij|ai-aj,其中 1≤i

證明設(shè)同余方程組(3.2)有解x0.則對(duì)任意 1≤i

反之,設(shè)dij |ai-aj,1≤i

則x1=r1=r1M0是x≡a1(modm1)的解.對(duì)于同余方程

注意到(m1,m2)|a2-a1以及a2-r1=(a2-a1)+q1m1,可得(m1,m2)|a2-r1,從而(3.3)式等價(jià)于

這個(gè)方程有解r2滿足0≤r2<.進(jìn)而x2=r1M0+r2M1滿足同余方程組

假設(shè)xn-1=r1M0+r2M1+···+rn-1Mn-2滿足同余方程組

考慮同余方程xn-1+Mn-1y≡an(modmn),即

注意到

以及

則有

于是[d1n,d2n,···,dn-1,n]|an-xn-1,即

進(jìn)而Mn-1y≡an-xn-1(modmn)有解,并且有一個(gè)rn滿足 0≤rn <.記

則xn為滿足假設(shè)條件的解.

假設(shè)x0也滿足同余方程組

則顯然有m1|xn-x0,m2|xn-x0,···,mn|xn-x0,從而M=[m1,m2,···,mn]|xn-x0,即xn≡x0(modM).

證畢.

秦九韶以絕頂智慧,在本質(zhì)上給出了定理3.2 的處理方式.這在那個(gè)沒有“素?cái)?shù)”概念的時(shí)代絕對(duì)是無中生有的創(chuàng)造.

下面我們給出定理3.2 的另一種證明.

首先,(3.2)式有解等價(jià)于整線性方程組

有解.對(duì)整線性方程組(3.3)的增廣矩陣做初等變換:

將上述初等變換后的矩陣記為A1.令整數(shù)s1,t1滿足s1m1+t1m2=(m1,m2).記α1=β1=.則

是n+2 階模方陣.計(jì)算A1B1得:

其中

將矩陣A1B1第2 行的倍依次加到第3,4,···,n行,再將第3 列乘以-1.得

其中x1==s1α1(a2-a1).將該矩陣記為A2.

令整數(shù)s2,t2滿足s2[m1,m2]+t2m3=([m1,m2],m3)=[(m1,m3),(m2,m3)].記

則

是n+2 階模方陣.計(jì)算A2B2得:

其中

將矩陣A2B2第3 行的倍依次加到第4,5,···,n行,再將第4 列乘以-1,則可得矩陣

其中

將上述矩陣記作A3.繼續(xù)下去,令整數(shù)si,ti,1≤i≤n-1 滿足

重復(fù)上面的操作,可得矩陣

由定理2.5 的(2.2)–(2.4)的討論知,整線性方程組(3.3)有整數(shù)解當(dāng)且僅當(dāng)

當(dāng)條件(3.4)滿足時(shí),由

可得[m1,m2,···,mi]|xi,1≤i≤n-2.又

則有d1n|(an-a1).若

則由(an-a1)=(an-aj)+(aj-a1),有

故有

從而djn|(an-aj).由n的一般性,可得

反之,若(3.5)成立,需證條件(3.4)也成立.

對(duì)n進(jìn)行歸納,只需考慮n時(shí)的情形.首先由歸納假設(shè)知

由此可得

當(dāng)2≤j≤n-1 時(shí),有

4 多元一次同余方程組的一些結(jié)果

4.1 一些引理

在開始我們的主要結(jié)論的證明之前,先給出兩個(gè)引理.

引理4.1 設(shè)整數(shù)a,b,c滿足(a,b)=1,(a,c)=1.則有(a,bd)=(a,d),(a,bc)=1.

證明當(dāng)a=0 時(shí),b=±1,顯然(a,bd)=(a,d).當(dāng)a0 時(shí),有

進(jìn)一步地,有

證畢.

引理4.2 設(shè)非零整數(shù)d1,d2,···,dr滿足d1|d2|···|dr,m為一整數(shù).記ai=,bi=,1≤i≤r.則有

證明首先,由d1|d2|···|dr知(di,m)|(dr,m).又由(ai,bi)==1,可得

繼而由引理4.1 知(a1a2···ar,br)=1.

再對(duì)r進(jìn)行歸納.當(dāng)r=2 時(shí),

假設(shè)(a1a2···ar-1,a1a2···ar-2br-1,···,b1b2···br-1)=1.則

證畢.

4.2 兩類多元一次同余方程組

定理4.1 設(shè)m為整數(shù).對(duì)同余方程組

記

設(shè)A的不變因子為d1,d2,···,dr,的不變因子為e1,e2,···es,s=r或s=r+1.則同余方程組(4.1)有解的充要條件是

(1)當(dāng)s=r時(shí),?1≤i≤r,(di,m)=(ei,m);

(2)當(dāng)s=r+1時(shí),?1≤i≤r,(di,m)=(ei,m),且m|es.

證明(4.1)式有解等價(jià)于整線性方程組

有解.

記A的j級(jí)子行列式對(duì)應(yīng)的矩陣為Aj,則矩陣

總有i(i≥j)級(jí)子行列式,其對(duì)應(yīng)的矩陣形如

又對(duì)任意1≤i≤r,有

由引理4.2 可得

同理可得

(1)當(dāng)s=r時(shí),由(4.3)–(4.5)可知,(4.2)有解的充要條件為

由此可得(4.2)有解的充要條件為?1≤i≤r,(di,m)=(ei,m).

(2)當(dāng)s=r+1時(shí),首先由(1)知?1≤i≤r,有(di,m)=(ei,m),故只需考慮r+1 級(jí)行列式的最大公因數(shù).此時(shí),有

且

故有

從而m=(er+1,m),即m|er+1.因此我們得到(4.2) 有解的充要條件為:?1≤i≤r,有(di,m)=(ei,m),且m|es.

證畢.

定理4.2 設(shè)m是正整數(shù),A=的不變因子為d1,d2,···,dr.若同余方程組Ax≡b(modm)有解,則它有(d1,m)···(dr,m)m(n-r) 個(gè)解.

證明考慮整線性方程組

記

則有l(wèi)階模矩陣U及n階模矩陣V,使得

從而

設(shè)當(dāng)r+1≤i≤l時(shí)di=0.則有整數(shù)si,ti滿足sidi+tim=(di,m).記αi=,βi=.則有模方陣

其中

使得

其中

記C=C1C2···Cl,則有

于是,(4.6)式等價(jià)于

即

記

則有

即

則由V是模方陣及所有的βi均取值m知,

由此可得(x1,x2,···,xn) 有(d1,m)(d2,m)···(dr,m)mn-r種取值,即(4.6) 的解的個(gè)數(shù)為(d1,m)(d2,m)···(dr,m)mn-r.

證畢.

定理4.3 設(shè)m1,m2,···,ml是兩兩互素的正整數(shù).則下面的同余方程組

有解當(dāng)且僅當(dāng)對(duì)每個(gè)1≤i≤l,同余方程

有解,亦即

證明若同余方程組(4.7)有解,則對(duì)每個(gè)1≤i≤l,同余方程

有解等價(jià)于整線性方程

有解.又存在模矩陣Vi,使得

故(4.8)有解當(dāng)且僅當(dāng)

有解,這等價(jià)于

反之,若對(duì)每個(gè)1≤i≤l,同余方程

有解,記為xi,從而(x1,x2,···,xn)為(4.7)的一組解.

證畢.

推論4.1 記正整數(shù)M=m1m2···ml,ki=(ai1,ai2,···,ain,mi)min-1.若(4.7)有解,則它在模M下有k1k2···kl個(gè)解.

證明由定理4.2 知(4.8)有(ai1,ai2,···,ain,mi)min-1個(gè)解.又由定理3.1 知(4.9)在模M下有唯一解,因此在模M下(4.7)有k1k2···kl個(gè)解.

5 一個(gè)遺留問題

對(duì)于任意的正整數(shù)m1,m2,···,ml,同余方程組

何時(shí)有解,在有解時(shí)如何求解? 這是一個(gè)仍需思考的問題.

當(dāng)然,我們可以先把(5.1)里的模m1,m2,···,ml統(tǒng)一為[m1,m2,···,ml]=m,將(5.1)演變?yōu)?/p>

再用上一節(jié)的方法來求解.

特別地,對(duì)看似簡單的同余方程組

當(dāng)m1,m2,···,ml不互素時(shí),該如何求解?