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

檢索策略