《用矩阵的初等行变换求N个整数的最大公因子.doc》由会员分享，可在线阅读，更多相关《用矩阵的初等行变换求N个整数的最大公因子.doc（9页珍藏版）》请在三一文库上搜索。
1、用矩阵的初等行变换求N个整数的最大公因子 摘 要：初等变换是高等代数中重要的内容之一，在数学学习中体现出很大的实用性。本文在常规方法（提取公因数法、分解质因数法等）的基础上,运用最大公因子的理论知识和矩阵的初等行变换，简便有效地求出N个数的最大公因子。其意义在于体现这种方法的优越性,促进此类问题的研究。关键词：初等行变换；整数；最大公因子Using the Matrixs Elementary Row Transformationto Solve the Greatest Common Factor of N IntegerAbstract: Elementary transformation
2、 is one of the important components in higher algebra and shows great practical applicability in mathematics learning. On the basis of conventional methods (i.e. the common factor withdrawal, prime factor decomposition, etc), this paper puts forward a simple method for effectively working out the gr
3、eatest common factor of N integer by adopting the theory of the greatest common factor and elementary row transformation. The significance of this method lies in its superiority and can promote research on this kind of problems. Key words: elementary row transformation; integer; greatest common fact
4、or1 引言初等数论的基础是整除理论，而整除理论的中心内容又是最大公因子理论.最大公因子理论看起来似乎很简单，但它的内容却是十分的重要.解线性方程组中引入矩阵1，不仅为解线性方程组带来极大的方便，同时也发展和完善了矩阵理论本身，丰富了矩阵理论的应用.不定方程2是初等数论的一个重要内容，而求N个数的最大公因子又是研究不定方程的一个必不可少的部分.在研究不定方程时，往往需要求出最大公因子，特别是求N（N3）个整数的最大公因子，那么根据不定方程的有关理论，求出最大公因子就可以断定方程是否有解. 而在求最大公因子时，通常的方法都是利用提取公因数法、分解质因数法、辗转相除法等3，这些方法的缺点是计算量过
5、大，步骤繁琐.尤其是在求N（N）个整数的最大公因子时，需要进行N-1次的运算4. 文献1、4、6、10中将整数的最大公因子扩充到多项式的最大公因式，而且求最大公因式的方法甚多，如提取公因数法、分解质因数法、辗转相除法等.目前，国内外的研究还出现了用计算机语言编写出程序，只需在电脑上输入N个多项式（整数），就可以求出最大公因式（最大公因子）.还有研究将整数的最大公因子扩充到矩阵的最大公因子（左最大公因子和右最大公因子）等.文中的其它文献也相应地介绍了最大公因子的求法及应用等理论知识，但这些求最大公因子的方法都具有一定的局限性，并且计算量过大，步骤繁琐，学生学习时容易出错，从而不易有效求出最终结果
6、. 本文利用矩阵的初等行变换求N个数的最大公因子，从而大大地改进了辗转相除法等方法所表现出来的缺点.2 预备知识求最大公因子都是在整数范围内进行的，这里明确指出，下文所涉及到的数都是指整数. 此外，还需要给出以下定义、引理等基础知识.定义1 设是n个整数，如果那么就称为的公因子定义25 设是n个不全为0的整数，那么的公因子中的最大的称为的最大公因子，记作当=1时，用表示的因子中最大的定义3 设矩阵A是 mn矩阵，若A中的元素均为整数，则称A为mn整数矩阵.定义46 主对角线上的元素全为1，其它元素都为0的矩阵称为n级单位矩阵.记作.定义57 称下列变换为整数矩阵的初等行变换.1. 互换整数矩阵
7、的第行第行，记作；2. 用整数k乘以矩阵的第行，记作；3. 把整数矩阵的第行乘以K以后加到第行，记作. 注：定义5中的K只能是中某一数的整数倍，目的是保证变换前后都是整数矩阵，且第一行元素的最大公因子也保持不变.或者用通俗的语言定义就是：矩阵的初等行变换是指对矩阵进行下列三种变换：1. 互换矩阵两行的位置（对换变换）；2. 用非0常数遍乘矩阵的某一行（倍乘变换）；3. 将矩阵的某一行遍乘一个常数k加到另一行（倍加变换）上.引理18 (最大公因子的性质定理)若是n个不全为0的数，则1.（）=（）；2.（）=（）；3.（）=. 由引理可知，要求N个整数的最大公因子，可以转化为求N个非负整数的最大公
8、因子；在求N个整数的最大公因子时，这N个整数的位置可以任意交换，而它们的最大公因子保持不变；求最大公因子时，把其中一个数的S倍加到其它整数上，最大公因子也保持不变.引理29 设0，则有引理3 （） （）.注1 引理2表明，求一组数的最大公因子时，可以通过提出这组数的公因子的方法来逐步求出例如：注2 引理3表明，求多个数的最大公因子，可以由求两个数的最大公因子来逐步求出例如： 由以上三式得：.定理1 若b是任一整数，则(0,b)=b.证明：b|0 ,b|b. b是0与 b的公因子. 又b的最大公因子是b. 0 与b的最大公因子就是b. 即（0，b）=b.推论1 若b 是任意整数，则（0，b ）=
9、|b|.推论2 若b 是任意整数，则（0,0,0,b）=|b|.注 推论1、推论2的证明方法和定理1相同.这里不再给出证明过程.定理210 设、b 、c是三个不全为0的整数，且 = bq + c，则(,b)=( ,c).证明：设=（,b）, =(b,c)， 则 ,. -bq.（整除的性质） 又=bq+c. c=-bq， |c. 是b与c的公因子 (,|c )， =(b,c) , 即 . (公因子小于或等于最大公因子) 下面证明 . =（b,c）. |b, |c， |bq+c， |， 是与 b 的公因子， (| , |b) (,b)=. 即 . (公因子小于或等于最大公因子) 由、得 =. 即（
10、,b）=(b,c). 注 c 满足0cb 或者cb均可.3主要结果及证明定理 设是一个一行n列整数矩阵，是一个n级单位矩阵，A= B=那么整数矩阵A经过有限次的矩阵初等行变换，一定可以化为整数矩阵B，且.注1 矩阵B中，除第一列的元素以外，其它的元素是任意的，它们不一定相同.注2 不全为0.（如果全为0，那么求n个数的最大公因子是没有意义的）.证明：假设，且均是非负数.反复利用矩阵的初等行变换，将这n个整数逐步化小，至到把这n-1个整数化作0为止.例如，将第一行乘以-k(k=1,2,)后加到第二行，第三行，第n行，然后再用数字最小的那一行乘以-k(k=1,2,)后，再分别加到其余的n-1行上，
11、如此继续下去，最终就可以把矩阵A化为矩阵B.即矩阵A经过有限次的矩阵初等行变换，一定可以化为矩阵B的形式.如果没有和这n个整数不全为0这两个条件，那么我们可以根据预备知识中的引理1来调整它们的顺序，把它们全部都化为非负整数.下面详细证明.上述过程中，即从矩阵A化为矩阵B的过程，是严格按照矩阵的初等行来变换的，由引理1可知，上述的每一步变换都不改变矩阵A中第一列元素的最大公因子.因此.由推论2知.所以 . 小结：由上述定理的证明过程得知,利用矩阵的初等行变换求解个整数的最大公因子的一般步骤如下:1. 根据引理1的理论知识，首先要把负整数变为非负整数.（如果这个整数中没有负整数的，则省略该步骤.）
12、2.将这个非负整数作为第一列，并在其右边放上一个级单位矩阵，组合成一个的整数矩阵. 即构造形如A的矩阵.3.利用矩阵的初等行变换把矩阵A化为矩阵B的形式.4.最后求出的最大公因子为.注 在把矩阵A化为矩阵B（即步骤3）的过程中，唯一的目标就是把这个数化为0，不需要考虑其它元素的变化情况.利用该定理就可以较方便快捷地求出n个整数的最大公因子.它的理论依据就是预备知识中的定理2，其实最根本的理论依据还是辗转相除法，只不过该定理是利用了矩阵的初等行变换这一工具，从而大大地简化了求解过程，特别是在n(n3)个较大整数的最大公因子时，更能体现出这种方法的优越性.下面将以例题来说明.4 应用举例例1 求
13、1008，1260，-882，1134的最大公因子.分析：方法一（矩阵的初等行变换法） 因为（-1008，1260，-882，1134）=（1008，1260，882，1134）.所以，要求-1008，1260，-882，1134的最大公因子，只需要求1008，1260，882，1134的最大公因子即可.所以，（1008，1260，882，1134）=126.（-1008，1260，-882，1134）=126.方法二（分解质因数法）根据最大公因子的性质同样有：（-1008，1260，-882，1134）=（1008，1260，882，1134）. 1008=2222337 =24327.12
14、60=223357=223257.882=23377=23272.1134=233337=2347.所以，（1008，1260，882，1134）=2327=126.（-1008，1260，-882，1134）=126.小结：比较这两种解法，用分解质因数法解题并不是难点，但是计算步骤过多过繁，容易出错.而矩阵的初等行变换法，不仅方便快捷、条理清楚、思路清晰，解题过程也很清晰.如果说数字再大一些，用分解质因数法就显得更加繁琐. 例2 用矩阵的初等行变换求73,5767,4453,8906的最大公因子.分析：要求73,5767,4453,8906的最大公因子，首先是构造形如A的矩阵，再利用矩阵的初
15、等行变换把它化为形如B的矩阵，从而求出它们的最大公因子.即进一步推导如下：最后得到(73,5767,4453,8906)=73.小结：该题的解题过程条理清楚、思路清晰.虽然用提取公因数法、分解质因数法、辗转相除法都可以求解出该题的最终结果，但是运算量较大、步骤过多、过于繁琐。 5 总结求最大公因子的方法甚多.从理论上说，文中的例1、例2均可以根据引理2，采用提取公因数法来求解，也可以根据引理3，采用辗转相除法来求解.只是这两个例题中的整数都比较大，要提取它们的公因数，这样运算量将会很大.如果采用辗转相除法，每一次只能求出两个整数的最大公因子，然后再和第三个数求最大公因子，依此类推，求个数的最大
16、公因子，就需要进行次的运算.由于大量的运算，步骤过多，当然就免不了出错，从而不容易求出最终结果.即使是利用计算机程序来求解，得预先编出一定的程序，而且使用者还得熟练计算机的基本操作.因此，利用计算机程序来求最大公因子，同样具有一定的局限性.唯有利用矩阵的初等行变换的求解方法能解决以上这些方法的缺点，该方法条理清楚、思路清晰、运算简单，这是提取公因数法、分解质因数法、辗转相除法等方法不可替代的.特别是在求多个较大整数的最大公因子时，更能体现出该方法的优越性.现代数学中，很多新的成果来自于学科之间的交叉研究.比如近年来的费尔兹数学奖中的研究成果尤为典型.对于最大公因子的求解方法，可能在与其它数学学
17、科交叉性研究时，能找到更多有效的解法. 鉴于本人知识水平有限，还有很多不足之处.对于此类问题，还有待以后作进一步的研究.参考文献1 乐茂华.高等代数M.南京：南京大学出版社，2002：154155.2 闵嗣鹤，严士健.初等数论M.北京：高等教育出版社，1995：3233.3 潘承洞，潘承彪.简明数论M.北京：北京大学出版社，1998：6164.4 李正彪，李祥.求多项式最大公因式的一种新方法J. 曲靖师范学院学报.2004，19（3）：4547.5 北京教育学院师范教研室.整数的基础知识M.北京：北京出版社，1982：1819.6 北京大学数学系几何与代数教研室小组.高等代数M.北京：高等教育出版社，2002：169170.7 李正彪，余波.用矩阵的初等列变换求解多元线性不定方程J.云南民族大学学报.2005，21（2）：7982.8 李正彪.关于两个数论定理的思考J.曲靖师范学院学报.2005，20（3）：2830.9 潘承洞，潘承彪.初等数论M.北京：北京大学出版社，1992：3334.10 杨刚.最大公因式的矩阵求法J.甘肃科学学报.2003，15（3）：1518.指导教师评语：