關于一次同余方程組的注記

石文章 劉合國

(1.湖北大學數學與統計學學院,武漢,430062?2.海南大學數學與統計學院,?？?570228)

1 引言

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

本文將從整數矩陣的模變換出發,研究在一般條件下,

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

本文采用文獻[1,5,6]的標準符號.

2 預備知識

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

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

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

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

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

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

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

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

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

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

定理2.1 又可表述成:經一系列初等變換,可將一矩陣變成相似標準形的形式.因為初等變換不改變矩陣的i級子行列式的最大公因數,因此可得下述定理:

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

結合(2.1)的相似標準形,可知

即為Am×n的i級子行列式的最大公因數.

定理2.4([1]) 任一矩陣的相似標準形是唯一的.

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

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

證明設A是m×n階矩陣,J是A的相似標準形,則存在m階模矩陣U和n階模矩陣V,使得

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

則Ax=b有解等價于下列方程

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

由上可知

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

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

考慮矩陣

由兩相似矩陣的所有i級子行列式的最大公因數相等,可得:當 1≤i≤r時,

即(2.4)成立.

證畢.

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

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

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

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

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

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

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

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

反之,設dij |ai-aj,1≤i

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

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

這個方程有解r2滿足0≤r2<.進而x2=r1M0+r2M1滿足同余方程組

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

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

注意到

以及

則有

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

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

則xn為滿足假設條件的解.

假設x0也滿足同余方程組

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

證畢.

秦九韶以絕頂智慧,在本質上給出了定理3.2 的處理方式.這在那個沒有“素數”概念的時代絕對是無中生有的創造.

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

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

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

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

是n+2 階模方陣.計算A1B1得:

其中

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

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

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

則

是n+2 階模方陣.計算A2B2得:

其中

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

其中

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

重復上面的操作,可得矩陣

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

當條件(3.4)滿足時,由

可得[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)也成立.

對n進行歸納,只需考慮n時的情形.首先由歸納假設知

由此可得

當2≤j≤n-1 時,有

4 多元一次同余方程組的一些結果

4.1 一些引理

在開始我們的主要結論的證明之前,先給出兩個引理.

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

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

進一步地,有

證畢.

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

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

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

再對r進行歸納.當r=2 時,

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

證畢.

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

定理4.1 設m為整數.對同余方程組

記

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

(1)當s=r時,?1≤i≤r,(di,m)=(ei,m);

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

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

有解.

記A的j級子行列式對應的矩陣為Aj,則矩陣

總有i(i≥j)級子行列式,其對應的矩陣形如

又對任意1≤i≤r,有

由引理4.2 可得

同理可得

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

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

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

且

故有

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

證畢.

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

證明考慮整線性方程組

記

則有l階模矩陣U及n階模矩陣V,使得

從而

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

其中

使得

其中

記C=C1C2···Cl,則有

于是,(4.6)式等價于

即

記

則有

即

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

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

證畢.

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

有解當且僅當對每個1≤i≤l,同余方程

有解,亦即

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

有解等價于整線性方程

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

故(4.8)有解當且僅當

有解,這等價于

反之,若對每個1≤i≤l,同余方程

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

證畢.

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

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

5 一個遺留問題

對于任意的正整數m1,m2,···,ml,同余方程組

何時有解,在有解時如何求解? 這是一個仍需思考的問題.

當然,我們可以先把(5.1)里的模m1,m2,···,ml統一為[m1,m2,···,ml]=m,將(5.1)演變為

再用上一節的方法來求解.

特別地,對看似簡單的同余方程組

當m1,m2,···,ml不互素時,該如何求解?