初等數(shù)論同余式.ppt

第四章 同余式 1 同余方程的基本概念 定義：設 , 則 叫做模m的同余方程 若 ,則稱n為同余方程的次數(shù)。 若 ， 則 稱為同余式的解 模m的一個完全剩余系中滿足同余方程的個數(shù)稱為滿足同余方程的解數(shù)。,注：對模m互相同余的解是同一個解。 例：同余式 次數(shù)為2， 是解， 也是解，因為 所以為同一解，解數(shù)是1，,為了求方程的解經(jīng)常有等價變形的問題， 對于同余方程同樣也有等價變形，即使原同余方程和新的同余方程互相等價的若干變換。常用的變換有 （1）移項運算是傳統(tǒng)的， （2）同余方程兩邊也可以加上模的若干倍。相當于同余方程兩邊加“零”。 （3）乘上一數(shù)k或除去一個數(shù)k，為了保持其同解性，必須（k ,m）=1，這一點和同余的性質(zhì)有區(qū)別。,例 等價于 等價于 即 ，,同余方程和不定方程一樣，我們同樣要考慮以下三個問題， 即有解的條件，解數(shù)及如何求解， 一般地說，對于一般的同余方程，由于僅有有限個解，只要把模m的一個完全剩余系一一代入即可，滿足同余方程的就是解。 但當模較大或次數(shù)較高時應尋求簡潔而實用的解法.,這一章主要討論 1、一次同余方程axb(mod m) 、一次同余方程組 xb1(mod m1) xb2(mod m2) xbk(mod mk) 的求解。, 2 一次同余方程 一次同余方程的一般形式為 axb(mod m)， 有 2.1定理：a,b為整數(shù)， ，則 axb(mod m)有解的充要條件是(a,m)|b,若有解則有d=(a,m)個關于模m的解,證明：由同余的定義知axb(mod m)等價于不定方程ax=b-my，而此不定方程有解的充要條件是(a,m)|b。在有解的情況下，設不定方程的解為 此時同余方程有d個解，為 因當 時，,2.2 一次同余方程axb(mod m)的解法。 （1）化為不定方程ax+my=b 例：解同余式 解 因為(45,132)=321,所以同余式有3個解. 化簡為等價的同余方程 我們再解不定方程15x-44y=7,得到一解(21,7)., 方程3個解為 即為,2) 利用歐拉定理 若(a,m)=1,則有 axb(mod m),兩邊同乘 ，則有 即 因為 所以,例: 解同余式 解：因為(8,11)=1,所以由歐拉定理 有,(3)用形式分數(shù) 定義1：當（a，m）=1時，若ab 1(modm)，則記b (modm)稱為形式分數(shù)。 根據(jù)定義和記號， 有性質(zhì) 1、 2、（d，m）=1，且 ，則 利用形式分數(shù)的性質(zhì)把分母變成1，從而求出一次同余式的解。,例：解一次同余方程 解：（17，25）=1，原同余方程有解，利用形式分數(shù)的性質(zhì)，同余方程解為,3 一次同余方程組的解法 定義:如下(*)稱為一次同余方程組 xb1(mod m1) xb2(mod m2) （*） xbk(mod mk) 有解判定定理：同余方程組（*）有解的充要條件是,下面給出k=2時的證明.,證: 若 (1)有解,則有 (2) 即 反之由(1)得 代入(2)有 因為 由一次同余方程有解條件知t有解,即同余方程組有解.,下面給出一個例子，并用代入法求解 例：解一次同余式組 解：因為(4,6)=2|3-1,所以有解,由(1)式得x=3+4t代入(2)得 即 得 代入x=3+4t 得 即 為一次同余式組的解。,下面我們給出模兩兩互素的情形，此時顯然滿足有解的條件，即 孫子定理：設 兩兩互素， 則同余式(*)組的解為 其中,證明：因為 兩兩互素， 所以有 中的 存在，又對任意的 有 有 所以 即是(*)的解 若 是滿足 (*)的兩個整數(shù)，則有 又 ,所以有 ,即 ,說明是惟一解。,例：解一次同余式組 解 :因為7，8,9兩兩互素，可以利用孫子定理. m=504, 進而有 所以有 是原一次同余式組的解。,注：若給出的同余方程組不是標準形式，必須注意化為標準形式，同時我們得到的有解的判別定理及求解方法都是在這一標準形式得到的。 同余方程組（1）有解的條件 (mi ,mj) bi-bj ，1i，jk 。 在使用時一定要對所有的組合進行驗算，進行有解的判別,求解一次同余方程組（*）有兩種方法： 待定系數(shù)法和孫子定理,二種方法各有特長。待定系數(shù)法適應的范圍較廣，對模沒有什么要求。孫子定理有一個具體的公式，形式也較漂亮。但對模要求是兩兩互素。 次數(shù)大于1的同余方程稱為高次同余方程，一般地高次同等方程可轉化一系列的高次同余方程組。然后將每一個高次同余方程的解都求出，最后利用孫子定理可求出原高次同余方程的解。,4 高次同余方程 定義1、次數(shù)大于1的同余方程稱為高次同余方程 對一般模的高次同余方程我們要通過“小?！焙汀敖荡巍钡姆椒▉淼玫揭话隳５母叽瓮喾匠痰慕狻?1、小模：即把一般模高次同等方程轉化為一系列模兩兩互素的高次同余方程組，即有 定理：設 ， 兩兩互素， 則 （1） 等價于下面方程組 （2） 設 和 的解數(shù)為 則有 下面來看證明.,證明：若 是（1）的解，即 則 從而有 ，即 即（1）的解就是（2）的解， 反之若 是（2）的解，則有 即 從而有 由于 兩兩互素，所以 ， 從而 有 即 即（2）的解也是（1）的解。,又由于（2）中第i個方程有 個解，則（2）一共可組合成 個一次同余式組，由孫子定理每一個同余式組有惟一解，所以有 個解，又由于（1）（2）的等價性，所以有,例：同余方程 解：原同余方程等價于同余方程組 即有 所以有4解，由孫子定理為,由于 所以 等價于同余方程組 從而從理論上說只要能解 即可，而由性質(zhì)可知若x是 的解，則一定是 的解 所以只要在 的解中 找 的解。 所以理論上只要解素數(shù)模 同余方程即可。,對素數(shù)模同余方程，可以降次，看下面的 定理：設p是素數(shù)， 是整系數(shù)多項式，設 是 的一個解，則有 （1） 則存在整數(shù)t使得 是 的解。 （2） 且 ， 則 當t=0，1，2P-1時， 都是 的解。,證明：由已知 是 的解，可設 代入 ，則有 兩邊同除 得 由 所以上式有惟一解， 代入x有 是 的解。 又若 且 ，則（*）對任意t都成立。即當t=0，1，2P-1時， 都是 的解。從而證明了定理。,例：解方程 解：因為 的解為 即x=2+3t，因為 由定理因為有 所以當t=0，1，2時，即 都是方程的解。,例：解方程 解：因為 等價于 其解為 因 令x=1+5t代入 有 即 即 即有 代入x=1+5t有,所以有 代入 有 兩邊同除25有 有 代入x有 即 是方程的解。 同理從 可得到另一解（作練習） 從上可知解 最后可歸結為解 即可， 下面討論 的解法。,5 素數(shù)模同余方程 （*）,定理：同余方程（*）或者有P個解，或者與一個次數(shù)不超過p-1次的素數(shù)模同余方程等價。 證：由多項式除法，存在q（x）和r（x）使得 由費馬定理 因此若 的系數(shù)全為p的倍數(shù)，則同余方程（*）有p個解，若 的系數(shù)不都是p的倍數(shù)，則 的次數(shù)不超過p-1次，且對任意的x有是 ，即同余方程（*）等價 證畢。,定理2： 設同余方程（*）有k 個不同的解 , 則對于任意的x有 , 其中 是一個次數(shù)為n-k的整系數(shù)多項式，且它的 的系數(shù)為 注:這個定理同一般方程類似,有一個 ,則從 f(x)中就可分解出 下面來看證明.,證：由多項式除 ,因 有 ，即 , 令 有 由于 是有k 個不同的解，所以有 (i=2,3,k),由歸納假設有 代入得有 證畢。,由定理2我們可得到下面的推論 推論1： p是素數(shù)，對任意的x有 證：由歐拉定理 有解，且其解為1,2p-1 由定理2知即得。,推論2(威爾遜定理）： p是素數(shù)，則有 證：由推論1 令x=p代入則有， 反之若 ,則m是素數(shù)。（自己證明） 注：所以威爾遜定理可用來判定一個數(shù)是否為素數(shù)。,定理3：同余方程（*）的解數(shù)不超過它的次數(shù)。 證：假設同余方程（*）有n+1個解，設為 由定理2知，對前n個解有 對第n+1個解有 由于 ,所以有i使得 和已知矛盾，所以假設錯誤。即同余方程（*）的解數(shù)不超過它的次數(shù)。,定理4： 同余方程（*）有n個解的充要條件是存在q（x）和r（x），使得 r(x)的次數(shù)小于n. 證：必要性 由多項式除法，存在q（x）和 使得 若同余方程（*）有n個解，由費馬定理有 ,i=1,2,