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

课题:矩阵方法在初等数论问题解决中的应用课题研究一:矩阵在多元一次不定方程求通解中的应用不定方程组是指未知量的个数多于方程个数的方程组。在大约1500年以前,我国古代数学家张丘建在他编写的《张丘建算经》里,曾经提出并解决了“百钱买百鸡”这个有名的数学问题:“今有鸡翁一值钱五,鸡母一值钱三,鸡雏三值钱一,凡百钱买百鸡,同鸡翁、鸡母、鸡雏各几何?”若设鸡翁、鸡母、鸡雏的个数分别为x,y,z,则由题意可得三元一次不定方程(*)进一步将方程(*)转化为三元一次整系数不定方程组(#)那么求鸡翁、鸡母、鸡雏的个数问题等价于求三元一次整系数不定方程组(#)的非负整数解的问题。下面将提出求多元一次不定方程组的整数解的一种简便算法:所谓多元一次不定方程,就是可以写成下列形式的方程:ax+ax+…+ax=N,(1)其中a,a,…,a,N都是整数,n≥2,并且不失一般性,我们可以假定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|,方程dt+ax+…+ax=N有解,设其一解为t,x,…,+ax=(a,a=d,上式有解,设其一解为x,x,则ax+ax+ax+…+ax=dt+ax+…+ax=,x,…,x是(1)式的解。证完下面举例说明:例:求9x+24y-5z=1000的一切解。解:(9,24)=3,(3,-5)=1,故方程有解。考虑方程9x+24y=3t,即3x+8y=t及3t-5z==0,±1,±2,…,v=0,±1,±2,….消去t,得x=6000+15v-8u,y=-2000-5v+3u,z=1000+,计算过程复杂,计算量较大,所以我们可以通过高等数学的工具来解决这个问题。下面我们引入矩阵方法求解不定方程(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=(10…0,(bA是可逆矩阵,,(2中的整系数矩阵A满足上面(a(b两个条件,则(2是(1),t,…,t,由(2确定的x,x,…,x都是(1的解,事实上(a,a,…,a)=(a,a,…,a)A=(10…0=1故ax+ax+…+ax=1,即x,x,…,x是(,x,…,x是(1的整数解,要证存在一组整数t,t,…,t满足(,我们考察A,由(b知A是整系数矩阵,由(a知A的第一行恰是(a,a,…,a),又由x,x,…,x是(1的解,故ax+ax+…+ax==,其中c,c,…,c是整数令t=c(i=1,2,…,n-1,则有A=A=AA=这就是我们所要证明的。至于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,…,(3的通解为t,t,…,:例:求9x+24y-5z=1000的一切解解:由故通解为(t,tZ通过一般方法与矩阵方法解n元一次不定方程的对比,我们可以很清楚地看到,矩阵方法的优势,既简单又明确,这不失为一个不错的方法。课题研究二:矩阵在解决一元一次同余式组问题的应用在我国古代的《孙子算经》(纪元前后)里已经提出了这种形式的问题,并且很好的解决了它,孙子算经里所提出的问题之一如下:“今有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二,