矩阵方法在初等数论问题解决中的应用.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+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元一次不定方程是比较麻烦的,计算过程复杂,计算量较大,所以我们可以通过高等数学的工具来解决这个问题。
下面我们引入矩阵方法求解不定方程
式的任何一组整数解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也是整系数矩阵.
反之,我们有下面