关于一次同余方程组的注记

石文章 刘合国

(1.湖北大学数学与统计学学院,武汉,430062;2.海南大学数学与统计学院,海口,570228)

1 引言

中国剩余定理是中国古代数学的一项光辉成就,它是线性同余方程组理论的一个核心内容,也是数论的一条基本原理.我们知道,一个整系数方程ax=b有解,当且仅当对任意的正整数m,同余方程ax≡b(modm)有解.引入同余的概念后,利用同余的理论和思想,可以大大简化数论中的相关问题.关于线性同余方程组理论的研究已有颇多成果,参见文献[1,5,6].文献[2]利用整数矩阵的初等变换证明了中国剩余定理,并提供了一个求解的途径.文献[1]第二章给出了多元一次同余方程有解的充要条件,并在有解时给出了解的个数.

本文将从整数矩阵的模变换出发,研究在一般条件下,

的求解问题.利用矩阵的不变因子给出多元一次同余方程组Ax≡b(modm)有解的一个充要条件,进而给出该同余方程组在有解情况下解的个数,由此自然地得到模互素的多元一次同余方程组有解的充要条件及解的个数.

本文采用文献[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不互素时,该如何求解?