1、用矩阵的初等行变换求 N 个整数的最大公因子数学系20021112班 高兴龙指导教师 铁 勇摘 要：初等变换是高等代数中重要的内容之一，在数学学习中体现出很大的实用性。本文在常规方法（提取公因数法、分解质因数法等）的基础上,运用最大公因子的理论知识和矩阵的初等行变换，简便有效地求出 N 个数的最大公因子。其意义在于体现这种方法的优越性,促进此类问题的研究。关键词：初等行变换；整数；最大公因子Using the Matrixs Elementary Row Transformationto Solve the Greatest Common Factor of N IntegerAbstract
2、: Elementary transformation 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 eff
3、ectively working out the greatest 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; in
4、teger; greatest common factor1 引言初等数论的基础是整除理论，而整除理论的中心内容又是最大公因子理论.最大公因子理论看起来似乎很简单，但它的内容却是十分的重要.解线性方程组中引入矩阵 1，不仅为解线性方程组带来极大的方便，同时也发展和完善了矩阵理论本身，丰富了矩阵理论的应用.不定方程 2是初等数论的一个重要内容，而求 N 个数的最大公因子又是研究不定方程的一个必不可少的部分.在研究不定方程时，往往需要求出最大公因子，特别是求N（N 3）个整数的最大公因子，那么根据不定方程的有关理论，求出最大公因子就可以断定方程是否有解. 而在求最大公因子时，通常的方法都是利用提取
5、公因数法、分解质因数法、辗转相除法等 3，这些方法的缺点是计算量过大，步骤繁琐.尤其是在求 N（N ）个3整数的最大公因子时，需要进行 N-1 次的运算 4. 文献1 、4、6、10中将整数的最大公因子扩充到多项式的最大公因式，而且求最大公因式的方法甚多，如提取公因数法、分解质因数法、辗转相除法等.目前，国内外的研究还出现了用计算机语言编写出程序，只需在电脑上输入 N 个多项式（整数） ，就可以求出最大公因式（最大公因子）.还有研究将整数的最大公因子扩充到矩阵的最大公因子（左最大公因子和右最大公因子）等.文中的其它文献也相应地介绍了最大公因子的求法及应用等理论知识，但这些求最大公因子的方法都具
6、有一定的局限性，并且计算量过大，步骤繁琐，学生学习时容易出错，从而不易有效求出最终结果. 本文利用矩阵的初等行变换求 N 个数的最大公因子，从而大大地改进了辗转相除法等方法所表现出来的缺点.2 预备知识求最大公因子都是在整数范围内进行的，这里明确指出，下文所涉及到的数都是指整数. 此外，还需要给出以下定义、引理等基础知识.定义 1 设 是 n 个整数，如果 那么 就称为a,21 12,ndada的公因子na,2定义 25 设 是 n 个不全为 0 的整数，那么 的公因子中a,21 na,21的最大的称为 的最大公因子，记作 当 =1 时，用 表na, nad,11示 的因子中最大的1a定义 3
7、 设矩阵 A 是 mn 矩阵，若 A 中的元素均为整数，则称 A 为 mn 整数矩阵.定义 46 主对角线上的元素全为 1，其它元素都为 0 的 矩阵n10称为 n 级单位矩阵.记作 .nE定义 57 称下列变换为整数矩阵的初等行变换.1. 互换整数矩阵的第 行第 行，记作 ；ij),(jip2. 用整数 k 乘以矩阵的第 行，记作 ；k3. 把整数矩阵的第 行乘以 K 以后加到第 行，记作 .ij)(jki注：定义 5 中的 K 只能是 中某一数的整数倍，目的是保证变换前后都na,21是整数矩阵，且第一行元素的最大公因子也保持不变.或者用通俗的语言定义就是：矩阵的初等行变换是指对矩阵进行下列
8、三种变换：1. 互换矩阵两行的位置（对换变换） ；2. 用非 0 常数遍乘矩阵的某一行（倍乘变换） ；3. 将矩阵的某一行遍乘一个常数 k 加到另一行（倍加变换）上.引理 18 (最大公因子的性质定理)若 是 n 个不全为 0 的数，则a,21.（ ）=（ ） ；n,1 na,212.（ ）=（ ） ；njiaa,1 21,aajin3.（ ）= . i,12 ),121(snii 由引理可知，要求 N 个整数的最大公因子，可以转化为求 N 个非负整数的最大公因子；在求 N 个整数的最大公因子时，这 N 个整数的位置可以任意交换，而它们的最大公因子保持不变；求最大公因子时，把其中一个数的 S
9、倍加到其它整数上，最大公因子也保持不变.引理 29 设 0，则有m1212(,)(,).k kbmb 引理 3 （ ）i123123(,),);kkaa （ ） .i ,),(, 1rkkrk a注 1 引理 2 表明，求一组数的最大公因子时，可以通过提出这组数的公因子的方法来逐步求出例如： 6)1,2()3,2(6),(32)9,6()8,( 注 2 引理 3 表明，求多个数的最大公因子，可以由求两个数的最大公因子来逐步求出例如： ),150,6(),106(2),3(2,35,2),( 1,)71,(,由以上三式得：.1)5,06(定理 1 若 b 是任一整数，则(0,b)=b.证明：b|
10、0 ,b|b.b 是 0 与 b 的公因子.又b 的最大公因子是 b.0 与 b 的最大公因子就是 b.即（0，b）=b.推论 1 若 b 是任意整数，则（0，b ）=|b|.推论 2 若 b 是任意整数，则（0,0,0,b）=|b|.注 推论 1、推论 2 的证明方法和定理 1 相同.这里不再给出证明过程.定理 210 设 、b 、c 是三个不全为 0 的整数，且 = bq + c，则( ,b)=( aaa,c).a证明：设 =（ ,b）, =(b,c)， 则 , .1d2dd|1b| -bq.（整除的性质）|a又 =bq+c. c= -bq， |c.1d 是 b 与 c 的公因子 ( ,
11、|c )，| bd|1 =(b,c) , 1d2即 . (公因子小于或等于最大公因子 ) 2下面证明 .1d2 =（b,c）. |b, |c， 2d |bq+c， | ， 2da 是 与 b 的公因子， ( | , |b) 2da2 ( ,b)= . 2da1即 . (公因子小于或等于最大公因子 ) 1由、得 = .d2即（ ,b）=(b,c). a注 c 满足 0cb 或者 cb 均可.3 主要结果及证明定理 设 是一个一行 n 列整数矩阵， 是一个 n 级单位矩阵，na121),( nEA= B=nE2 *0a那么整数矩阵 A 经过有限次的矩阵初等行变换，一定可以化为整数矩阵 B，且.aa
12、n),(21注 1 矩阵 B 中，除第一列的元素以外，其它的元素是任意的，它们不一定相同.注 2 不全为 0.（如果 全为 0，那么求 n 个数的最大公因子na,21 na,21是没有意义的）.证明：假设 ，且 均是非负数.反复利用矩阵naa21 na,21的初等行变换，将 这 n 个整数逐步化小，至到把 这 n-1 个, na,2整数化作 0 为止.例如，将第一行乘以-k(k=1,2,)后加到第二行，第三行，第 n行，然后再用数字最小的那一行乘以-k(k=1,2,)后，再分别加到其余的 n-1 行上，如此继续下去，最终就可以把矩阵 A 化为矩阵 B.即矩阵 A 经过有限次的矩阵初等行变换，一
13、定可以化为矩阵 B 的形式.如果没有 和 这 n 个整数不全为 0 这两个条件，那么naa21 a,21我们可以根据预备知识中的引理 1 来调整它们的顺序，把它们全部都化为非负整数.下面详细证明.aan),(21上述过程中，即从矩阵 A 化为矩阵 B 的过程，是严格按照矩阵的初等行来变换的，由引理 1 可知，上述的每一步变换都不改变矩阵 A 中第一列元素的最大公因子.因此.),(21na )0,( 由推论 2 知.a)0,( 所以 . aan),(21小结：由上述定理的证明过程得知,利用矩阵的初等行变换求解 个整数的最大n公因子的一般步骤如下:1. 根据引理 1 的理论知识，首先要把负整数变为
14、非负整数.（如果这 个整数中没有负整数的，则省略该步骤.）2.将这 个非负整数作为第一列，并在其右边放上一个 级单位矩阵，组合成n n一个 的整数矩阵. 即构造形如 A 的矩阵.)1(3.利用矩阵的初等行变换把矩阵 A 化为矩阵 B 的形式.4.最后求出 的最大公因子为 .na,21 a注 在把矩阵 A 化为矩阵 B（即步骤 3）的过程中，唯一的目标就是把这na,32个数化为 0，不需要考虑其它元素的变化情况.利用该定理就可以较方便快捷地1求出 n 个整数的最大公因子.它的理论依据就是预备知识中的定理 2，其实最根本的理论依据还是辗转相除法，只不过该定理是利用了矩阵的初等行变换这一工具，从而大
15、大地简化了求解过程，特别是在 n(n3)个较大整数的最大公因子时，更能体现出这种方法的优越性.下面将以例题来说明.4 应用举例例 1 求 1008，1260，-882， 1134 的最大公因子.分析：方法一（矩阵的初等行变换法）因为（-1008，1260，-882，1134）=（1008，1260，882，1134）.所以，要求-1008，1260，-882，1134 的最大公因子，只需要求1008，1260，882，1134 的最大公因子即可. 1028731610258371610134826 )42(37)41(3 pp所以，（1008，1260，882，1134）=126.（-1008
16、，1260，-882，1134）=126.方法二（分解质因数法）根据最大公因子的性质同样有：（-1008，1260，-882，1134）=（1008，1260，882，1134）.1008=2 2 2 2 3 3 7=24 32 7.1260=2 2 3 3 5 7=22 32 5 7.882=2 3 3 7 7=2 32 72.1134=2 3 3 3 3 7=2 34 7.所以，（1008，1260，882，1134）=2 32 7=126.（-1008，1260，-882，1134）=126.小结：比较这两种解法，用分解质因数法解题并不是难点，但是计算步骤过多过繁，容易出错.而矩阵的初等
17、行变换法，不仅方便快捷、条理清楚、思路清晰，解题过程也很清晰.如果说数字再大一些，用分解质因数法就显得更加繁琐.例 2 用矩阵的初等行变换求 73,5767,4453,8906 的最大公因子.分析：要求 73,5767,4453,8906 的最大公因子，首先是构造形如 A 的矩阵，再利用矩阵的初等行变换把它化为形如 B 的矩阵，从而求出它们的最大公因子.即 12045317108964537)2(3p进一步推导如下： 1204379291120435147)37()3(2 pp最后得到(73,5767,4453,8906)=73.小结：该题的解题过程条理清楚、思路清晰.虽然用提取公因数法、分解质因数法、辗转相除法都可以求解出该题的最终结果，但是运算量较大、步骤过多、过于繁琐。 5 总结求最大公因子的方法甚多.从理论上说，文中的例 1、例 2 均可以根据引理 2，采用提取公因数法来求解，也可以根据引理 3，采用辗转相除法来求解.只是这两个例题中的整数都比较大，要提取它们的公因数，这样运算量将会很大.如果采用辗转相除法，每一次只能求出两个整数的最大公因子，然后再和第三个数求最大公因子，依此类推，求 个数的最n 1204379)24(1p
