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

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