畢業(yè)論文 同余方程的解法

1、包頭師范學(xué)院本 科 畢 業(yè) 論 文題 目： 同余方程的解法 學(xué)生姓名： 學(xué) 號： 專 業(yè)： 數(shù)學(xué)與應(yīng)用數(shù)學(xué) 班 級: 指導(dǎo)教師： 李曉冬 二 一 年 四 月摘要：本文論述了同余方程的基本概念及同余方程的一些基本性質(zhì)與解法，主要對一次同余方程的解法進(jìn)行了探討，特別是對一次同余方程的歐拉定理算法，歐幾里德算法等七種解法進(jìn)行了比較與分析，并介紹了同余方程組、孫子定理、素?cái)?shù)模的同余方程，模 的同余方程的解法。關(guān)鍵詞： 同余 同余方程 孫子定理 abstract：this paper mainly discusses the basic concepts of congruence equations

2、and congruence equation some of the basic nature of solution,and highlights the remainder theorem,solution of the congruence equation,mod congruence equation solution,congruence equation of primes mode solution,etc.key words: congruence congruence equation remainder theorem目錄引言11.同余與同余方程的基本性質(zhì)21.1 同余

3、的概念與基本性質(zhì)21.2同余方程的概念與性質(zhì)32.一次同余方程的解法42.1 的情況42.2 的情況73.同余方程組的解法83.1簡單同余方程組的解法83.2 孫子定理94.高次同余方程的的解法114.1素?cái)?shù)模的同余方程114.2模pa的同余方程12總結(jié)：17參考文獻(xiàn)18致謝：19引言對于同余方程的解法國內(nèi)外的數(shù)學(xué)家們均對其做出了非常全面與細(xì)致的研究。在我國古代的數(shù)學(xué)名著孫子算經(jīng)中就較早的給出了同余方程的算法即著名的“孫子定理”。我國宋代的大數(shù)學(xué)家秦九詔，也在他的杰作數(shù)書九章中也對同余方程的解法進(jìn)行了系統(tǒng)的研究。教材中對于同余方程的解法雖然給出了一些方法，但對其研究還不夠全面不徹底。所以對于同

4、余方程的解法進(jìn)行歸納總結(jié)，從而作進(jìn)一步的研究就顯得特別重要。1.同余與同余方程的基本性質(zhì)1.1 同余的概念與基本性質(zhì)定義1 給定一個(gè)正整數(shù)，如果用去除兩個(gè)整數(shù)所得的余數(shù)相同，那么稱對模同余，記作；否則，稱同余.記作定理1 設(shè)是一個(gè)正整數(shù)，是兩個(gè)整數(shù)，則的充要條件是存在一個(gè)整數(shù)使得定理2 模同余是等價(jià)關(guān)系，即 （i）（自反性）對任意整數(shù),； （ii）（對稱性）若, 則； （iii）（傳遞性）若, 定理 3 整數(shù)同余的充分必要條件是除的余數(shù)相同.定理4 設(shè)一個(gè)整數(shù)， 是四個(gè)整數(shù).如果 , 從而， 定理 5 若, 則 定理6設(shè)一個(gè)正整數(shù)，.如果則 定理7 設(shè)一個(gè)正整數(shù)，, 則 定理 8 設(shè)一個(gè)正整數(shù)

5、，,如果整數(shù)則定理9 設(shè)是一個(gè)正整數(shù)，, 如果.定理10 設(shè)是一個(gè)正整數(shù)， , , 則定理11 設(shè)是一個(gè)正整數(shù)，.1.2同余方程的概念與性質(zhì)定義2 設(shè)是整系數(shù)多項(xiàng)式，稱 (1)是關(guān)于未知數(shù)的模的同余方程，簡稱為模的同余方程。若，則稱為次同余方程。定義3 設(shè)是整數(shù)，當(dāng)時(shí)式(1)成立，則稱是同余方程的解。凡對于模同余的解，被視為同一個(gè)解。同余方程(1)的解數(shù)是指它的關(guān)于?；ゲ煌嗟乃薪獾膫€(gè)數(shù)，也即在模的一個(gè)完全剩余系中的解的個(gè)數(shù)。由定義3，同余方程(1)的解數(shù)不超過定理12 下面的結(jié)論成立：() 設(shè)是整系數(shù)多項(xiàng)式，則同余方程(1)與等價(jià)；() 設(shè)是整數(shù)，則同余方程(1)與等價(jià)；() 設(shè)是素?cái)?shù)，都

6、是整系數(shù)多項(xiàng)式，又設(shè)是同余方程(1)的解，則必是同余方程的解。 2.一次同余方程的解法定理13 同余方程() 若有唯一解() 若， 沒有解() 若， 有個(gè)解2.1 的情況2.1.1觀察法在模的完全剩余系中考慮同余式的解，此方法適用在當(dāng)模較小時(shí)或方程具有特殊形式的一次同余方程里例1：的解為2.1.2歐拉定理算法由歐拉定理有，而可得既得：為所求的解。此解法適合較小或較易求解例2：解解，2.1.3化為不定方程的解法有解存在整數(shù)使得。即不定方程有解。此解法對模的要求較低。例3：解解：原方程對應(yīng)的不定方程為其通解為（對任意的整數(shù)），所以2.1.4減小模數(shù)的解法對于 此時(shí)，然后去掉中的倍數(shù)不斷將模變小此時(shí)

7、若有解，則為的解。經(jīng)過幾次轉(zhuǎn)換后一般可以用觀察法求解，在遞推出原方程的解。此方法適合模數(shù)較大的同余方程。例4：解同余式解：原同余式即是：，解同余式：得：，所以原同余式的解是：2.1.5歐幾里得算法可借用輾轉(zhuǎn)相除法求整數(shù)的最大公因數(shù)的方法，結(jié)合同余式的性質(zhì)，可轉(zhuǎn)化為一個(gè)形如的同解方程。當(dāng)利用恒等變形將變小，直至將的系數(shù)化為1.若, 且模數(shù)較大時(shí), 可用取余的辦法, 將變小, 然后求出解。例5: 解同余式.解: , 原同余式有1 個(gè)解。,而, 。,而,即為原同余式的解。若, 且中至少有一個(gè)數(shù)大于m , 可根據(jù)同余知識, 將化小, 再用方法去解。例6: 解解: ,原同余式化為:,而,。又,。為原同余

8、式的解。2.1.6分式法先把寫成的形式（這里是一種形式的寫法）然后用與互素的數(shù)陸續(xù)的乘又端的分子和分母，目的在于把分母的絕對值變小，直到變成1為止。此方法使用模不太大如三位數(shù)或三位數(shù)以內(nèi)的。例7：解同余是解2.1.7威爾遜定理解法為素?cái)?shù)，由威爾遜定理有：此方法適用模為素?cái)?shù)且模不能太大。例8：解解2.2 的情況， 有個(gè)解2.2.1化為法對于先用去除同余式，在按的情況去解。例9：求的解解 原方程有4個(gè)解。用4去除同余式得：而，原同余式的解為2.2.2消去的系數(shù)解同余式逐次消去的系數(shù)例10： 解同余式。解：因?yàn)椋嗍接袀€(gè)解。原同余式可化簡為，與的公因數(shù)與互質(zhì)，可消去公因數(shù)，同余式進(jìn)一步化簡為：。與

9、的公因數(shù)與互質(zhì)，可消去公因數(shù)，同余式可化簡為：，是的倍數(shù)故：。原同余式的個(gè)解為：。利用輾轉(zhuǎn)相除法消去 的系數(shù)對于系數(shù)較大、較復(fù)雜的同余式, 可以采取輾轉(zhuǎn)相除法消去 的系數(shù)。例11：解同余式解：因?yàn)橥嗍接袀€(gè)解?；啠?，用輾轉(zhuǎn)相除法，將上述過程反演得到：所以：因?yàn)橥嗍降?個(gè)解為：3.同余方程組的解法3.1簡單同余方程組的解法對于同余方程組 （1）當(dāng)時(shí)的簡單解法。例12. 解同余方程組。 (2)解 : 將(2)的前一式乘以2后一式乘以3再相減得到再代入(2)的前一式得到即同余方程組(2)的解是。3.2 孫子定理定理14(孫子定理) 設(shè)是正整數(shù)， 記， ，則存在整數(shù)，使得， 并且 （3）是同余方程

10、組(1)對模的唯一解，即若有使方程組(1)成立，則。 定理15 同余方程組(1)有解的充要條件是 定理16 設(shè)，其中是兩兩互素的正整數(shù)，是整系數(shù)多項(xiàng)式，以與分別表示同余方程 與 的解的個(gè)數(shù)，則例13. 求整數(shù)，它被除的余數(shù)分別是解:是同余方程組的解。根據(jù)孫子定理，取則因此所求的整數(shù)例14. 解同余方程。 (4)解: 因?yàn)?，所以，由定?6可知，同余方程(4)等價(jià)于同余方程組 (5) (6) (7)分別解同余方程(5)，(6)，(7)得到解，同余方程(4)的解可轉(zhuǎn)化為下面的方程：，其中或，或。利用孫子定理，取則。將所有可能的取值代入上式，得到方程(4)的全部解是，。4.高次同余方程的的解法4.1

11、素?cái)?shù)模的同余方程設(shè)是整系數(shù)多項(xiàng)式，是素?cái)?shù)， 。定理17 設(shè)若同余方程 (1)有個(gè)不同的解則對于任意的整數(shù)有，其中是一個(gè)次數(shù)為的整系數(shù)多項(xiàng)式，并且它的項(xiàng)的系數(shù)是定理18 同余方程(1)的解數(shù)定理19 同余方程(1)與一個(gè)次數(shù)不超過的質(zhì)數(shù)模同余式等價(jià)。定理20 設(shè)，則同余方程有個(gè)解的充要條件是存在整數(shù)多項(xiàng)式和，的次數(shù)使得定理21 (定理)若是素?cái)?shù)，則 例15. 判定同余方程是否有三個(gè)解。解: 因?yàn)椋?，原方程與即等價(jià)。由于所以，由定理20和定理18可知，原方程的解數(shù)小于。例16. 解同余方程。解: 由定理，又因?yàn)橐虼?，由定?9原同余方程等價(jià)于：即 。 （2）將分別代入方程（2）進(jìn)行驗(yàn)證，可知這

12、個(gè)同余方程解是4.2模pa的同余方程求解模的同余方程可以轉(zhuǎn)化為對模的同余方程的求解。若是同余方程 (1)的解，則它必是方程 (2)的解，因此，必有與相應(yīng)的方程(2)的某個(gè)解，使，此處，是某個(gè)適當(dāng)?shù)恼麛?shù)。定理22設(shè)是素?cái)?shù)，是整數(shù)，是整系數(shù)多項(xiàng)式，又設(shè)是同余方程(2)的一個(gè)解。以表示的導(dǎo)函數(shù)。() 若，則存在整數(shù)，使得 (3)是同余方程(1)的解。() 若并且，則對于，式(3)中的是方程(1)的解。由定理，可以把解同余方程(1)，轉(zhuǎn)化為解同余方程。 (4)由方程(4)的解，利用定理，可以求出方程的解，再利用定理，又可以求出方程的解，ll，直到求出方程(1)的解。推論1 使用定理的記號，() 若是同

13、余方程(4)的解，并且，則存在，使得是同余方程(1)的解。() 若與同余方程(4)沒有公共解，則對于任意的整數(shù)，同余方程(1)與(4)的解數(shù)相同。例17. 解同余方程。解: 根據(jù)定理16 原同余方程等價(jià)于同余方程組， (5)。 (6)先解同余方程(5)。同余方程的解是。令并代入方程(5)，得到， (7)由定理22()這是一個(gè)對于任何整數(shù)t都成立的同余式，所以，方程(7)的解是，于是方程(5)的解是。 (8)再解同余方程(6)。用去驗(yàn)證，得到(6)的解是。因此，原同余方程的解是下面六個(gè)同余方程組的解：利用孫子定理解這六個(gè)方程組，記，則。將，。例18. 解同余方程。 (9)解: 同余方程 (10)

14、有兩個(gè)解。令， (11)代入同余方程， (12)得到，。 (13)于是，將式(11)與式(13)聯(lián)合，得到方程(12)的解。 (14)將式(14)中的代入同余方程(9)，得到 ，。將上式與(14)聯(lián)合，得到同余方程(9)的一個(gè)解。 從同余方程(10)的另一個(gè)解出發(fā)利用上述方法，可以求出同余方程(9)的另一個(gè)解為。例19. 解同余方程。 (15)解: 若，則方程(15)的解是。若，則方程(15)的解是。若，則同余方程(15)，即，的解必是奇數(shù)，設(shè)，則同余方程(1)成為，。 (16)同余方程(16)的解是，即，所以，方程(15)的解是，即?？偨Y(jié)：本文應(yīng)用前人的研究成果，對同余方程的常用解法進(jìn)行了系

15、統(tǒng)的歸納總結(jié)，并對其解法進(jìn)行了進(jìn)一步的研究優(yōu)化。其主要對一次同余方程的解法進(jìn)行了詳細(xì)的介紹，其次對用孫子定理來解同余方程組做了初步的總結(jié)，最后敘述了素?cái)?shù)模及模的同余方程的解法，但本文只是講了一些同余方程的常見解法，希望讀者在這方面有更好更多的見解。參考文獻(xiàn) 柯召，孫琦.數(shù)論講義上冊m. 高等教育出版社,北京,2001年 閔嗣鶴,嚴(yán)士健.初等數(shù)論第三版m.高等教育出版社,北京,2003年 潘乘洞、潘乘彪.初等數(shù)論m.北京大學(xué)出版社第二版,北京，2003年 杜德利.基礎(chǔ)數(shù)論m.周仲良,譯.上?？萍汲霭嫔?上海1982年 劉合義.談數(shù)論中的同余及其應(yīng)用j.衡水師專學(xué)報(bào),2002年 原新生.一次同余方程的幾種解法j.牡丹江教育學(xué)院學(xué)報(bào)