用矩陣的初等行變換求N個整數(shù)的最大公因子

1、用矩陣的初等行變換求n個整數(shù)的最大公因子 摘 要：初等變換是高等代數(shù)中重要的內容之一，在數(shù)學學習中體現(xiàn)出很大的實用性。本文在常規(guī)方法（提取公因數(shù)法、分解質因數(shù)法等）的基礎上,運用最大公因子的理論知識和矩陣的初等行變換，簡便有效地求出n個數(shù)的最大公因子。其意義在于體現(xiàn)這種方法的優(yōu)越性,促進此類問題的研究。關鍵詞：初等行變換；整數(shù)；最大公因子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 引言初等數(shù)論的基礎是整除理論，而整除理論的中心內容又是最大公因子理論.最大公因子理論看起來似乎很簡單，但它的內容卻是十分的重要.解線性方程組中引入矩陣1，不僅為解線性方程組帶來極大的方便，同時也發(fā)展和完善了矩陣理論本身，豐富了矩陣理論的應用.不定方程2是初等數(shù)論的一個重要內容，而求n個數(shù)的最大公因子又是研究不定方程的一個必不可少的部分.在研究不定方程時，往往需要求出最大公因子，特別是求n（n3）個整數(shù)的最大公因子，那么根據(jù)不定方程的有關理論，求出最大公因子就可以斷定方程是否有解. 而在求最大公因子時，通常的方法都是利用提取公因數(shù)法、分解質因數(shù)法、輾轉相除法等3，這些方法的缺點是計算量過

5、大，步驟繁瑣.尤其是在求n（n）個整數(shù)的最大公因子時，需要進行n-1次的運算4. 文獻1、4、6、10中將整數(shù)的最大公因子擴充到多項式的最大公因式，而且求最大公因式的方法甚多，如提取公因數(shù)法、分解質因數(shù)法、輾轉相除法等.目前，國內外的研究還出現(xiàn)了用計算機語言編寫出程序，只需在電腦上輸入n個多項式（整數(shù)），就可以求出最大公因式（最大公因子）.還有研究將整數(shù)的最大公因子擴充到矩陣的最大公因子（左最大公因子和右最大公因子）等.文中的其它文獻也相應地介紹了最大公因子的求法及應用等理論知識，但這些求最大公因子的方法都具有一定的局限性，并且計算量過大，步驟繁瑣，學生學習時容易出錯，從而不易有效求出最終結果

6、. 本文利用矩陣的初等行變換求n個數(shù)的最大公因子，從而大大地改進了輾轉相除法等方法所表現(xiàn)出來的缺點.2 預備知識求最大公因子都是在整數(shù)范圍內進行的，這里明確指出，下文所涉及到的數(shù)都是指整數(shù). 此外，還需要給出以下定義、引理等基礎知識.定義1 設是n個整數(shù)，如果那么就稱為的公因子定義25 設是n個不全為0的整數(shù)，那么的公因子中的最大的稱為的最大公因子，記作當=1時，用表示的因子中最大的定義3 設矩陣a是 m×n矩陣，若a中的元素均為整數(shù)，則稱a為m×n整數(shù)矩陣.定義46 主對角線上的元素全為1，其它元素都為0的矩陣稱為n級單位矩陣.記作.定義57 稱下列變換為整數(shù)矩陣的初等行

7、變換.1. 互換整數(shù)矩陣的第行第行，記作；2. 用整數(shù)k乘以矩陣的第行，記作；3. 把整數(shù)矩陣的第行乘以k以后加到第行，記作. 注：定義5中的k只能是中某一數(shù)的整數(shù)倍，目的是保證變換前后都是整數(shù)矩陣，且第一行元素的最大公因子也保持不變.或者用通俗的語言定義就是：矩陣的初等行變換是指對矩陣進行下列三種變換：1. 互換矩陣兩行的位置（對換變換）；2. 用非0常數(shù)遍乘矩陣的某一行（倍乘變換）；3. 將矩陣的某一行遍乘一個常數(shù)k加到另一行（倍加變換）上.引理18 (最大公因子的性質定理)若是n個不全為0的數(shù)，則1.（）=（）；2.（）=（）；3.（）=. 由引理可知，要求n個整數(shù)的最大公因子，可以轉化

8、為求n個非負整數(shù)的最大公因子；在求n個整數(shù)的最大公因子時，這n個整數(shù)的位置可以任意交換，而它們的最大公因子保持不變；求最大公因子時，把其中一個數(shù)的s倍加到其它整數(shù)上，最大公因子也保持不變.引理29 設0，則有引理3 （） （）.注1 引理2表明，求一組數(shù)的最大公因子時，可以通過提出這組數(shù)的公因子的方法來逐步求出例如：注2 引理3表明，求多個數(shù)的最大公因子，可以由求兩個數(shù)的最大公因子來逐步求出例如： 由以上三式得：.定理1 若b是任一整數(shù)，則(0,b)=b.證明：b|0 ,b|b. b是0與 b的公因子. 又b的最大公因子是b. 0 與b的最大公因子就是b. 即（0，b）=b.推論1 若b 是任

9、意整數(shù)，則（0，b ）=|b|.推論2 若b 是任意整數(shù)，則（0,0,0,b）=|b|.注 推論1、推論2的證明方法和定理1相同.這里不再給出證明過程.定理210 設、b 、c是三個不全為0的整數(shù)，且 = 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列整數(shù)矩陣，是一個n級單位矩陣，a= b=那么整數(shù)矩陣a經(jīng)過有限次的矩陣初等行變換，一定可以化為整數(shù)矩陣b，且.注1 矩陣b中，除第一列的元素以外，其它的元素是任意的，它們不一定相同.注2 不全為0.（如果全為0，那么求n個數(shù)的最大公因子是沒有意義的）.證明：假設，且均是非負數(shù).反復利用矩陣的初等行變換，將這n個整數(shù)逐步化小，至到把這n-1個整數(shù)化作0為止.例如，將第一行乘以-k(k=1,2,)后加到第二行，第三行，第n行，然后再用數(shù)字最小的那一行乘以-k(k=1,2,)后，再分

11、別加到其余的n-1行上，如此繼續(xù)下去，最終就可以把矩陣a化為矩陣b.即矩陣a經(jīng)過有限次的矩陣初等行變換，一定可以化為矩陣b的形式.如果沒有和這n個整數(shù)不全為0這兩個條件，那么我們可以根據(jù)預備知識中的引理1來調整它們的順序，把它們全部都化為非負整數(shù).下面詳細證明.上述過程中，即從矩陣a化為矩陣b的過程，是嚴格按照矩陣的初等行來變換的，由引理1可知，上述的每一步變換都不改變矩陣a中第一列元素的最大公因子.因此.由推論2知.所以 . 小結：由上述定理的證明過程得知,利用矩陣的初等行變換求解個整數(shù)的最大公因子的一般步驟如下:1. 根據(jù)引理1的理論知識，首先要把負整數(shù)變?yōu)榉秦撜麛?shù).（如果這個整數(shù)中沒有負

12、整數(shù)的，則省略該步驟.）2.將這個非負整數(shù)作為第一列，并在其右邊放上一個級單位矩陣，組合成一個的整數(shù)矩陣. 即構造形如a的矩陣.3.利用矩陣的初等行變換把矩陣a化為矩陣b的形式.4.最后求出的最大公因子為.注 在把矩陣a化為矩陣b（即步驟3）的過程中，唯一的目標就是把這個數(shù)化為0，不需要考慮其它元素的變化情況.利用該定理就可以較方便快捷地求出n個整數(shù)的最大公因子.它的理論依據(jù)就是預備知識中的定理2，其實最根本的理論依據(jù)還是輾轉相除法，只不過該定理是利用了矩陣的初等行變換這一工具，從而大大地簡化了求解過程，特別是在n(n3)個較大整數(shù)的最大公因子時，更能體現(xiàn)出這種方法的優(yōu)越性.下面將以例題來說明

13、.4 應用舉例例1 求 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.方法二（分解質因數(shù)法）根據(jù)最大公因子的性質同樣有：（-1008，1260，-882，1134）=（1008，1260，882，1134）. 1008=22223

14、37 =24327.1260=223357=223257.882=23377=23272.1134=233337=2347.所以，（1008，1260，882，1134）=2327=126.（-1008，1260，-882，1134）=126.小結：比較這兩種解法，用分解質因數(shù)法解題并不是難點，但是計算步驟過多過繁，容易出錯.而矩陣的初等行變換法，不僅方便快捷、條理清楚、思路清晰，解題過程也很清晰.如果說數(shù)字再大一些，用分解質因數(shù)法就顯得更加繁瑣. 例2 用矩陣的初等行變換求73,5767,4453,8906的最大公因子.分析：要求73,5767,4453,8906的最大公因子，首先是構造形如

15、a的矩陣，再利用矩陣的初等行變換把它化為形如b的矩陣，從而求出它們的最大公因子.即進一步推導如下：最后得到(73,5767,4453,8906)=73.小結：該題的解題過程條理清楚、思路清晰.雖然用提取公因數(shù)法、分解質因數(shù)法、輾轉相除法都可以求解出該題的最終結果，但是運算量較大、步驟過多、過于繁瑣。 5 總結求最大公因子的方法甚多.從理論上說，文中的例1、例2均可以根據(jù)引理2，采用提取公因數(shù)法來求解，也可以根據(jù)引理3，采用輾轉相除法來求解.只是這兩個例題中的整數(shù)都比較大，要提取它們的公因數(shù)，這樣運算量將會很大.如果采用輾轉相除法，每一次只能求出兩個整數(shù)的最大公因子，然后再和第三個數(shù)求最大公因子

16、，依此類推，求個數(shù)的最大公因子，就需要進行次的運算.由于大量的運算，步驟過多，當然就免不了出錯，從而不容易求出最終結果.即使是利用計算機程序來求解，得預先編出一定的程序，而且使用者還得熟練計算機的基本操作.因此，利用計算機程序來求最大公因子，同樣具有一定的局限性.唯有利用矩陣的初等行變換的求解方法能解決以上這些方法的缺點，該方法條理清楚、思路清晰、運算簡單，這是提取公因數(shù)法、分解質因數(shù)法、輾轉相除法等方法不可替代的.特別是在求多個較大整數(shù)的最大公因子時，更能體現(xiàn)出該方法的優(yōu)越性.現(xiàn)代數(shù)學中，很多新的成果來自于學科之間的交叉研究.比如近年來的費爾茲數(shù)學獎中的研究成果尤為典型.對于最大公因子的求解方法，可能在與其它數(shù)學學科交叉性研究時，能找到更多有效的解法. 鑒于本人知識水平有限，還有很多不足之處.對于此類問題，還有待以后作進一步的研究.參考文獻1 樂茂華.高等代數(shù)m.南京：南京大學出版社，2002：154155.2 閔嗣鶴，嚴士健.初等數(shù)論m.北京：高等教育出版社，1995：3233.3 潘承洞，潘承彪.簡明數(shù)論m.北京：北京大學出版社，1998：6164.4 李正彪，李祥.求多項式最大公因式的一種新方法j. 曲靖師范學院學報.2004，19（3）：4547.5 北京教育學院師范