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

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

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

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

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

8、為求n個(gè)非負(fù)整數(shù)的最大公因子；在求n個(gè)整數(shù)的最大公因子時(shí)，這n個(gè)整數(shù)的位置可以任意交換，而它們的最大公因子保持不變；求最大公因子時(shí)，把其中一個(gè)數(shù)的s倍加到其它整數(shù)上，最大公因子也保持不變.引理29 設(shè)0，則有引理3 （） （）.注1 引理2表明，求一組數(shù)的最大公因子時(shí)，可以通過(guò)提出這組數(shù)的公因子的方法來(lái)逐步求出例如：注2 引理3表明，求多個(gè)數(shù)的最大公因子，可以由求兩個(gè)數(shù)的最大公因子來(lái)逐步求出例如： 由以上三式得：.定理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相同.這里不再給出證明過(guò)程.定理210 設(shè)、b 、c是三個(gè)不全為0的整數(shù)，且 = bq + c，則(,b)=( ,c).證明：設(shè)=（,b）, =(b,c)， 則 ,. -bq.（整除的性質(zhì)） 又=bq+c. c=-bq， |c. 是b與c的公因子 (,|c )， =(b,c) , 即 . (公因子小于或等于最大公因子) 下面證明 . =（b,c）. |b, |c， |bq+c， |， 是與 b 的公因子， (| , |b) (,b)=. 即 . (公因子小于或等于最大公因

10、子) 由、得 =. 即（,b）=(b,c). 注 c 滿(mǎn)足0cb 或者cb均可.3主要結(jié)果及證明定理 設(shè)是一個(gè)一行n列整數(shù)矩陣，是一個(gè)n級(jí)單位矩陣，a= b=那么整數(shù)矩陣a經(jīng)過(guò)有限次的矩陣初等行變換，一定可以化為整數(shù)矩陣b，且.注1 矩陣b中，除第一列的元素以外，其它的元素是任意的，它們不一定相同.注2 不全為0.（如果全為0，那么求n個(gè)數(shù)的最大公因子是沒(méi)有意義的）.證明：假設(shè)，且均是非負(fù)數(shù).反復(fù)利用矩陣的初等行變換，將這n個(gè)整數(shù)逐步化小，至到把這n-1個(gè)整數(shù)化作0為止.例如，將第一行乘以-k(k=1,2,)后加到第二行，第三行，第n行，然后再用數(shù)字最小的那一行乘以-k(k=1,2,)后，再分

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

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

13、.4 應(yīng)用舉例例1 求 1008，1260，-882，1134的最大公因子.分析：方法一（矩陣的初等行變換法） 因?yàn)椋?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.方法二（分解質(zhì)因數(shù)法）根據(jù)最大公因子的性質(zhì)同樣有：（-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.小結(jié)：比較這兩種解法，用分解質(zhì)因數(shù)法解題并不是難點(diǎn)，但是計(jì)算步驟過(guò)多過(guò)繁，容易出錯(cuò).而矩陣的初等行變換法，不僅方便快捷、條理清楚、思路清晰，解題過(guò)程也很清晰.如果說(shuō)數(shù)字再大一些，用分解質(zhì)因數(shù)法就顯得更加繁瑣. 例2 用矩陣的初等行變換求73,5767,4453,8906的最大公因子.分析：要求73,5767,4453,8906的最大公因子，首先是構(gòu)造形如

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

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