矩阵方法在初等数论问题解决中的应用.doc

课题：矩阵方法在初等数论问题解决中的应用课题研究一：矩阵在多元一次不定方程求通解中的应用不定方程组是指未知量的个数多于方程个数的方程组。在大约1500年以前，我国古代数学家张丘建在他编写的张丘建算经里，曾经提出并解决了“百钱买百鸡”这个有名的数学问题：“今有鸡翁一值钱五，鸡母一值钱三，鸡雏三值钱一，凡百钱买百鸡，同鸡翁、鸡母、鸡雏各几何？”若设鸡翁、鸡母、鸡雏的个数分别为x,y,z,则由题意可得三元一次不定方程 （*）进一步将方程（*）转化为三元一次整系数不定方程组 （#）那么求鸡翁、鸡母、鸡雏的个数问题等价于求三元一次整系数不定方程组（#）的非负整数解的问题。下面将提出求多元一次不定方程组的整数解的一种简便算法：所谓多元一次不定方程，就是可以写成下列形式的方程：ax+ax+ax=N， （1）其中a,a,a,N都是整数，n2，并且不失一般性，我们可以假定a,a,，a都不等于零。现在首先证明定理1（1）式有整数解的充分与必要条件是（a,a,a）|N。证明：设（a,a,a）=d.(i)若（1）式有解，即有n个整数x,x,x满足等式ax+ax+ + ax=N则由整数的可乘可加性定理，d|ax+ax+ax即d|N ,这就证明了条件的必要性。（ii）若d|N ,下面用数学归纳法证明（1）式有解。当n=2时，由二元一次方程有解的充分必要条件可得，（1）式有解。假设上述条件对n-1元一次不定方程是充分的，下证上述条件对n元一次不定方程也是充分的。令d=(a,a),则（d，a,a,a）=d|N.由归纳法假定，方程dt+ax+ax=N有解，设其一解为t,x,x.再考虑ax+ax=dt.由二元一次不定方程的充分必要条件及(a,a)=d，上式有解，设其一解为x,x，则ax+ax+ax+ +ax=dt+ax+ax=N.故x,x,x是（1）式的解。 证完下面举例说明：例 ： 求9x+24y-5z=1000的一切解。解 ：（9,24）=3，（3，-5）=1，故方程有解。考虑方程9x+24y=3t,即3x+8y=t及 3t-5z=1000.所以 其中u=0，1，2，v=0，1，2，.消去t，得x=6000+15v-8u,y=-2000-5v+3u,z=1000+3v.这就是我们所要求的结果对于传统方法求解n元一次不定方程是比较麻烦的，计算过程复杂，计算量较大，所以我们可以通过高等数学的工具来解决这个问题。下面我们引入矩阵方法求解不定方程(1) 式的任何一组整数解x，x，x都可以表示成：即 （2）（其中a，t都是整数，A成为（2）的整系数矩阵）下面我们引入通解的概念 定义 如果对于（1）的任何一组整数解x，x，x，有且只有一组整数t，t，t使（2）成立，并且对于任意一组整数t，t，t，由（2）得到的x，x，x都是（1）的整数解，那么就称（2）是（1）的通解.因此,当(2)是(1)的通解时,易知(2)中的整系数矩阵A应满足(a)（a,a,a）A=(1 0 0)，(b)A是可逆矩阵,且A也是整系数矩阵.反之,我们有下面的定理.定理2 如果(2)中的整系数矩阵A满足上面(a)(b)两个条件,则(2)是（1）的通解.证明 1) 对任意一组整数t，t，t,由(2)确定的x，x，x都是(1)的解,事实上（a,a,a）=（a,a,a）A=(1 0 0) =1故ax + ax + + ax =1，即x，x，x是(1)的解.2) 设x，x，x是(1)的整数解,要证存在一组整数t，t，t满足(2).为此,我们考察A,由(b)知A是整系数矩阵,由(a)知A的第一行恰是（a,a,a）,又由x，x，x是(1)的解,故ax+ax+ax=1.所以A=,其中c,c,，c是整数令t=c(i=1,2，n-1)，则有A=A=A A=这就是我们所要证明的。 至于t，t，t的唯一性，则是显然的。 下面给出n元一次不定方程的矩阵解法步骤。 对n元一次不定方程ax + ax + + ax = b， (3)则(3)有解（a,a,a）|b, 令a=da , i=1,，n； b=db则（3）化为ax + ax + + ax = b （4）此时 （ a，a， a）=1 ， 由（3）（4）同解，且则ax + ax + + ax =1的通解为t，t，t为任意整数.而(3)的通解为t，t，t为任意有理数. 下面仍举上面的例子说明：例：求9x+24y-5z=1000的一切解解: 由 故通解为 (t,t Z)通过一般方法与矩阵方法解n元一次不定方程的对比，我们可以很清楚地看到，矩阵方法的优势，既简单又明确，这不失为一个不错的方法。课题研究二：矩阵在解决一元一次同余式组问题的应用在我国古代的孙子算经（纪元前后）里已经提出了这种形式的问题，并且很好的解决了它，孙子算经里所提出的问题之一如下：“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？” “答曰二十三”。设x是所求物数，则依题意 X2(mod3),X 3(mod5),X2(mod7)。孙子算经里面所用的方法可以列表如下：除数余数最小公倍数衍数乘率各总答数最小答数323*5*7=1055*7235*2*2140+63+300=233233-2*105=23537*3121*1*3723*5115*1*2把这个结果加以推广就成为孙子定理：设m，m，m是k个两两互质的正整数，m= mmm,m=mM,i=1,2, ,k,则同余式组x b (mod m),x b (mod m),x b (mod m) （1）的解是xMMb+ MMb+MMb(modm), （2）其中MM1(modm), i=1,2, ,k.证明：由（m，m）=1,ij即得（M，m）=1，故知对每一M，有一M存在，使得MM1(modm)另一方面，m = mM，因此，m| M，ij，故： MMb b (mod m)即为（1）的解。若x,x是适合（1）式的任意两个整数，则x x (mod m), i=1,2, ,k,因（m，m）=1,于是x x (mod m),故（1）的解只有（2） 证完例题：运用孙子定理解同余式组x b (mod 5),x b (mod 6) x b (mod 7),x b (mod11)解：此时m=5*6*7*11=2310, M=6*7*11=462，M=5*7*11=385，M=5*6*11=330, M=5*6*7=210.解MM1(modm)，i=1,2,3，4得M=3， M =1，M =1，M=1.故x 3*462b+385 b+330 b +210 b (mod 2310)即为所求。以上为解同余式组的传统方法孙子定理法，即对含有n个同余式组（限定为形式）而言，通过计算求M，这样需要求解n个不定方程，以求出某一解作为M，计算量较大。本课题引进矩阵工具，并利用矩阵之初等变化求上述形式的同余式组的解。此法可以进行推广，即将上述同余式形式拓展为形式。定理1：设定同孙子定理（初等数论），令矩阵K= 对k施行整数矩阵的行初等变化，将k化为某一行为（1，x）形式，则xx (modm)即为原同余式组的解。证明：有条件知（M,M, M）=1.故存在uuuz,使uM+uM+uM=1.从而通过行初等变化可将k的某一行化为（1，）形式，取x=，则若(mod m)，i=1,2, ,k.则由孙子定理可知xx(mod m)即为原同余式组的解。事实上，由uM+uM+uM=1，当ij时，m/M.故上式即为+t=1。亦即(mod m), i=1,k.综合上述过程，可知结论成立。定理1是下述定理的特殊情况。定理2:设同余式组其中（a，m）=1, （m，m）=1,ij,i,j=1,k构造矩阵（整数型式）K= 对k施行整数矩阵的行初等变换，使k某一行变为（1，x）形式，则xx(mod m)为原同余式的解。特别地，如果（Ma,Ma, Ma）=1，则k可换为= 注：对孙子定理中要求的同余式组（即a=1时），由m，m，m两两互质，故（M,M, M）=1，再进行矩阵处理。证明：类似于定理1的证明，略例题解析：例1: 十一数之余三，七十二数之余二，十三数之余一，求此数。解：设此数为x，则原问题等价于同余式组由m=10296，M=936，M=936,M=792. 构造下列矩阵并进行初等变换：K= 故x 1730 (mod 10296)例2:“物不知其数”解：m=105,M=35,M=21,M=15.由K= 故解为x23(mod 105).例3：求相邻的四个整数，它们依次可被2，3，5，7整除解：设四个数分别为x-1，x,x+1,x+2,则由k= 则解为x-58851 (mod44100)29349（mod44100）从而可得求数为29348+a,29349+a,29350+a, 29351+a, 其中a=44100t（tz）比较课题研究二中的孙子定理的解法可以看出矩阵解法的简洁性