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

矩阵方法在初等数论问题解决中的应用.docx课题:矩阵方法在初等数论问题解决中的应用课题研究一:矩阵在多元一次不定方程求通解中的应用不定方程组是指未知量的个数多于方程个数的方程组。在人约1500年以前,我国古代数学家张丘建在他编写的《张丘建算经》里,曾经提出并解决了“百钱买百鸡”这个有名的数学问题:“今有鸡翁一值钱五,鸡母一值钱三,鸡雏三值钱一,凡百钱买百鸡,同鸡翁、鸡母、鸡雏各儿何?”若设鸡翁、鸡母、鸡雏的个数分别为x,y,z,则由题意可得三元一次不定方程兀+y+z=100{1(*)15x+3y+-z=1003进一步将方程(*)转化为三元一次整系数不定方程组x+y+z=10015x+9y+z=300那么求鸡翁、鸡母、鸡雏的个数问题等价于求三元一次整系数不定方程组(#)的非负整数解的问题。下面将提出求多元一次不定方程组的整数解的一种简便算法:所谓多元一次不定方程,就是可以写成下列形式的方程:aiX]+a2x2+-+awxz,=N,(1)其中a,,a2,-,an,N都是整数,n$2,并且不失一般性,我们可以假定a,,a2,-,J都不等于零。现在首先证明定理1(1)式有整数解的充分与必要条件是(aHa2,-,an)|NO证明:设(%,J,…,an)二d.(i)若(1)式有解,即有n个整数x;,x;,-,xn满足等式aiXi+a2X2+•••+%x'n二N贝!J由整数的可乘可加性定3,d|a1Xj+a2x2+---+anxn即d|N,这就证明了条件的必要性。(ii)若d|N,下面用数学归纳法证明(1)式有解。当n二2时,由二元一次方程有解的充分必要条件可得,(1)式有解。假设上述条件对叶1元一次不定方程是充分的,下证上述条件对n元一次不定方程也是充分的。令d2=(a!,a2),则(d?,a3,a4,•••,an)=d|,方程d2t2+a3x3+-+anxn=N有解,设其一解为t2,x3,-,x„.再考虑*a〕xl+a2x2=(ai,a2)=d2,上式有解,设其一解为x;,x;,则aix;+a2x2+a3x;+-+anxn=d2t2+a3x;+-+anxn=*,x2,•••,xn是(1)式的解。 证完下面举例说明:例:求9x+24y-5z=1000的一切解。解:(9,24)二3,(3,-5)二1,故方程有解。考虑方程及9x+24y=3t,即3x+8y二t3t-5z==3t-Su,y=—/+3w,1=2000+5%z=1000+3v,其中u=0,±1,±2,…,v二0,±1,±2,・・・.消去t,得x=6000+15v-8u,y二-2000-5v+3u,z=1000+,计算过程复杂,计算量较大,所以我们可以通过高等数学的工具来解决这个问题。下面我们引入矩阵方法求解不定方程(1)式的任何一组整数解X】,x2,…,:(其中%,°都是整数,A成为(2)的整系数矩阵)下面我们引入通解的概念定义如果对于(1)的任何一组整数解勒,x2,・・・,x”,有且只有一组整数t[,t2,…,使(2)成立,并且对于任意一组整数t],七2,…,t_],由(2)得到的X】,x2,…,X”都是(1)的整数解,那么就称(2)是(1),当(2)是(1)的通解时,易知(2)中的整系数矩阵A应满足(a,,a2,•••,an)A=(l0…0),A是可逆矩阵,口A-,⑵中的整系数矩阵A满足上面(a)(b)两个条件,则⑵是(1))对任意一组整数t],t?,…,t切,由(2)确定的X|,X2,乂口都是(1)的解,事实上a2,・・•,an)X2■■■=(且i,且2,•••,an)A(1、tl■■■=(10…0)<1、tl•■■=1<Xn>Jn・l)k^n-1)故£X】+a2x2+…+anxn=1,即X],x2,…,⑴)设X],X2,…,X"是(1)的整数解,要证存在一组整数t2,(2)・为此,我们考察X|X2由(b)矢口A"是整系数矩阵,由(a)知r的第一行恰是(aHa2,-,an),又,其中cHc2,由X],x2,…,Xn是⑴的解,故a,x1+a2x2+--+anx/I=*是整数令tj=Cj(i=l,2,…,n-1),则有<1、<1>z、At.■■■二A5■■■二AA-1X.••■二X2••■(tn・l)<Cn-l)kXn><Xn>这就是我们所要证明的。至于t],t2,…,tn」的唯一,性,则是显然的。下面给出n元一次不定方程的矩阵解法步骤。对n元一次不定方程a】Xj+a2x2+・••+anxn=b, (3)则⑶有解o(a,,a2,-,an)|