一次同余式解法的綜述

一次同余式的解法的綜述陳明丹（華南師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院廣州510070）【摘要】本文系統(tǒng)地將解一次同余式的各種解法集中在一起，如歐拉定理算法、代入求解法、消去系數(shù)法、不定方程求解法、不定方程求解法、分式法、威爾遜定理法、求s、t法、矩陣求法、“倒數(shù)”求法，這樣就使得學(xué)習(xí)者在學(xué)習(xí)一次同余式的時候有個系統(tǒng)的歸納總結(jié)，方便理解。關(guān)鍵詞：一次同余式；解法；歐拉定理；威爾遜定理；不定方程；綜述初等數(shù)論是師范院校數(shù)學(xué)專業(yè)學(xué)生的一門必修課，也是高中數(shù)學(xué)教師繼續(xù)教育的一項重要內(nèi)容，而同余式是初等數(shù)論中非常重要的一部分內(nèi)容，主要研究一次同余式、二次同余式、同余式組及高次同余式的解法及解數(shù)。[1]一次同余式是學(xué)習(xí)這一部分內(nèi)容的基礎(chǔ)，且結(jié)一次同余式是學(xué)習(xí)初等數(shù)論必須要掌握的解題方法。但是在嚴(yán)士鍵[2]的教材中只給出了如歐拉定理算法[3]等一些比較簡單的方法，而且比較散亂。本文旨在系統(tǒng)地整理解一次同余式的各種方法，以方便大家的學(xué)習(xí)。1.一次同余式axb(modm)的解法1.1同余式的解法1.1.1歐拉定理算法李曉東[1]和李婷[3]指出歐拉定理這種算法主要是運用歐拉定理，則有,則，則滿足同余式，故為同余式的解。李婷還指出這種解法在理論上較易分析，但當(dāng)模m較大時，求就涉及m的標(biāo)準(zhǔn)分解，此時這種解法在計算量上較為復(fù)雜，不宜進行計算機編程計算。所以這種解法更適合模m較小時，或較易求解時使用。王靖娜[4]給出了詳細(xì)的定理證明過程，以幫助大家的理解。1.1.2代入求解法代入求解法也稱為觀察法[3]，當(dāng)模m較小時，可以將模m的完全剩余系0、1、2……m-1代入到中，求出該同余式的解。當(dāng)模m較大時，則可以利用同余式的性質(zhì)[2]，將同余式的系數(shù)減少，而且有帶余除法定理[5]可保證系數(shù)在一個固定的范圍內(nèi)作為模m的余數(shù)，從而再用觀察法得出一次同余式的解。李婷[3]這種解法適用于多數(shù)情況，但是當(dāng)模m及x的系數(shù)較大時，計算量也會變得比較大，此時就不適合使用這種方法，而改用其他的方法。1.1.3消去系數(shù)法在同余式中，如果，則可以解出該同余式的解，因此，將x的系數(shù)消去是解一次同余式的最簡捷的方法[6]。如果在同余式中但能找到使得且，則根據(jù)同余的傳遞性質(zhì)有，可解出?；蛘哒业?，且有公因數(shù)，，則可根據(jù)引理將化簡為，按照此方法逐次消去x的系數(shù)。王迪吉、張維娟[6]把消去系數(shù)法分為三種，一是直接消去x的系數(shù)，一是逐次消去x的系數(shù)，還有一種是利用輾轉(zhuǎn)相除法消去x的系數(shù)。這三種方法對于很多種情況的同余式都可以求解。1.1.4不定方程求解法王迪吉，張維娟[6]還指出同余式有解的充分必要條件是不定方程有解，李婷[3]還指出這種方法對模m的要求較低而且易于利用計算機編程來求解同余式。1.1.5不定方程求解法當(dāng)時，可利用輾轉(zhuǎn)相除法求整數(shù)的最大公因數(shù)的方法，結(jié)合同余式的性質(zhì)，可以轉(zhuǎn)化為一個形如的同解方程，以達到求解的目的。[3]這種解法就叫做歐幾里德算法。這種解法本質(zhì)上是：當(dāng)時，利用恒等變形將變小，直至將x的系數(shù)變?yōu)?。[7]1.1.6分式法華羅庚[7]指出：對于，先把寫成的形式（這里的只是一種形式上的寫法），然后用與m互素的數(shù)陸續(xù)乘右端的分子和分母，目的在于把分母的絕對值變小，知道變?yōu)?為止。但是需要注意的是這里的只是一種形式符號，不能當(dāng)一般的分?jǐn)?shù)進行運算。更需要注意的是對的“分子”“分母”乘以不為零的整數(shù)或約去一個與模m互質(zhì)的數(shù)，否則所得出的結(jié)果可能不是原同余式的解。這種方法給出了一次同余式的形式解，較直觀。但是這種解法只適合于模m不太大時。[3]1.1.7威爾遜定理法威爾遜定理：p為質(zhì)數(shù)，則有。[3]當(dāng)為質(zhì)數(shù)，則由威爾遜定理有：,則有。[9]這種解法和歐拉定理解法一樣，也是給出了一次同余式的一組公式解，但是此時要求模p為質(zhì)數(shù)且不能太大，否則計算階乘時將比較麻煩。1.1.8求s、t法因為的充分必要條件是存在s、t使得，則對同余式有，所以有，即滿足同余式。[10]這種解法主要是要求出s、t，但是s、t在某些時候是不容易求出的。1.1.9矩陣求法毛毓球，陳永林[11]指出也可以用矩陣方法去解，此時可以把基本矩陣取為，再對A施以行初等變換，使它的某一行變?yōu)榈男问綍r，此時是原一次同余式的解。袁虎延[12]給出了五種類型的一次同余式的不同類型的矩陣的解法，這會使學(xué)習(xí)者更容易理解。1.1.10“倒數(shù)”求法我們知道，當(dāng)我們求解一元一次方程時，是通過恒等變形或同解變形，將一元一次方程化成最簡方程的形式，然后再用未知數(shù)x的系數(shù)的倒數(shù)去乘方程兩邊，得出方程的解。龍盛鼎[13]類比于這種解法，解一次同余式。設(shè)想在求解一次同余式的時候也引入未知數(shù)x的系數(shù)的“倒數(shù)”的概念。他定義：設(shè)是整數(shù)，m是一個給定的正整數(shù)，如果存在整數(shù)，使得，則稱為對于模m的倒數(shù)。則根據(jù)定理：若，令是對于模m的倒數(shù)，則一次同余式的解是。[14]1.2同余式的解法同余式的解法是基于同余式的解法，這種題目的解題步驟是[1]：、先判斷同余式是否有解，及解的個數(shù)。、再化為類型的同余式。、根據(jù)前面提到的各種方法求解類型的同余式。、在此基礎(chǔ)上寫出原同余式的所有解根據(jù)以上的步驟解題就可以求解出一次同余式的解。2．結(jié)論一次同余式的解法一直以來都有學(xué)者在研究，所以他們在這一方面已有很深入的研究，上面的這些解法就是他們對解一次同余式的理解，各種解法各有千秋，在使用的時候還需要靈活變通，根據(jù)不同的類型而選擇使用不同的方法，甚至是將各種方法融合在一起共同使用，以達到解題的目的。參考文獻：[1]李曉冬,.一次同余式解法的研究[J].陰山學(xué)刊(自然科學(xué)版),2006,(2).[2]嚴(yán)士健,閔嗣鶴.初等數(shù)論(第三版)[M]高等教育出版社,2003:74-76.[3]李婷.一次同余式解法的特點及其分析[J].黑龍江科技信息,2008,(19).[4]王靖娜.詳析一次同余式求解定理的證明[J].陜西教育(高教版),2009,(4).[5]張禾瑞，郝柄新.高等代數(shù)（第五版）[M].高等教育出版社，2007：31-32.[6]王迪吉,張維娟.關(guān)于一次同余式的解法[J].新疆師范大學(xué)學(xué)報(自然科學(xué)版),2007,(4).[7]華羅庚.數(shù)論導(dǎo)引[M].北京：高等教育出版社，1986,4:115-122.[8]李復(fù)中.初等數(shù)論選講[M].長春：東北師范大學(xué)出版社，1984,12:93-112.[9]柯召，孫琦.數(shù)論講義[M].北京：高等教育出版社，1986,4:115-122.[10]馮克勤，余紅兵.初等數(shù)論[M].北京：中國科技技術(shù)出版社，1999.[11]毛毓球，陳永林.求解不定方程與同余式（組）的矩陣方法[J].數(shù)學(xué)通報（北京師范大學(xué)出版社）,1990,(4).[12]袁虎廷.一次同余式的初等變換解法[J].山西大學(xué)學(xué)報(自然科學(xué)版),1998,(4).[13]龍盛鼎.一次同余式的另一解法[J].內(nèi)江師范學(xué)院學(xué)報,1987,(S1).[14]潘承洞，潘成彪.初等數(shù)論（第二版）[M].北京：北京大學(xué)出版社，2002：:162-167.

檢索策略