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

课题：矩阵方法在初等数论问题解决中的应用 课题研究一：矩阵在多元一次不定方程求通解中的应用 不定方程组是指未知量的个数多于方程个数的方程组。在大约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|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元一次不定方程是比较麻烦的，计算过程复杂，计算量较大，所以我们可以通过高等数学的工具来解决这个问题。 下面我们引入矩阵方法求解不定方程 式的任何一组整数解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,