第二講同余(數(shù)論復(fù)賽輔導(dǎo))

1、包頭市數(shù)學(xué)聯(lián)賽輔導(dǎo) 復(fù)賽數(shù)論初步選講-北重三中 樊增平第二講 同余一.基礎(chǔ)知識(shí)1.定義1. 設(shè)是正整數(shù)，若用去除整數(shù)，所得的余數(shù)相同，則稱與關(guān)于模同余，記作，否則稱與關(guān)于模不同余，記作.例如：， 等等。當(dāng)時(shí)，則稱是對(duì)模的最小非負(fù)剩余。對(duì)于固定的模，通常有下面的性質(zhì)：性質(zhì)1. 的充要條件是也即。性質(zhì)2.同余關(guān)系滿足以下規(guī)律：（1）（反身性）；（2）（對(duì)稱性）若，則；（3）（傳遞性）若，則；（4）（同余式相加）若，則；（5）（同余式相乘）若，則；注意： 反復(fù)利用（4）（5），可以對(duì)多于兩個(gè)的（模相同的）同余式建立加、減和乘法的運(yùn)算公式 ； 特別地，由（5）易推出：若，為整數(shù)且，則； 同余式的消去律

2、一般并不成立，即從未必能推出，可是我們卻有以下結(jié)果：若，則.由此可以推出：（6）若，則有，即在與互素時(shí)，可以在原同余式兩邊約去而不改變模.（7）若，則；（8）若，則；（9）若，則，特別地，若兩兩互素時(shí)，則有；性質(zhì)3.若，則；性質(zhì)4.設(shè)是系數(shù)全為整數(shù)的多項(xiàng)式，若，則。這一性質(zhì)在計(jì)算時(shí)特別有用：在計(jì)算大數(shù)字的式子時(shí)，可以改變成與它同余的小數(shù)字，使計(jì)算大大地簡(jiǎn)化。整數(shù)集合可以按模來分類，確切地說，若和模同余，則和屬同一類，否則不屬于同一類，每一個(gè)這樣的類稱為模的一個(gè)同余類。由帶余除法，任一整數(shù)必恰與0,1,，中的一個(gè)模同余，而0,1,，這個(gè)數(shù)彼此模不同余，因此模共有個(gè)不同的同余類， 例如，模2的同余

3、類共有兩個(gè)，即通常說的偶數(shù)類與奇數(shù)類，這兩類中的數(shù)分別具有形式和（為任意整數(shù)）.2. 定義2 （剩余類）設(shè)是正整數(shù)，把全體整數(shù)按對(duì)模的余數(shù)分成類，相應(yīng)的個(gè)集合記為：，其中每一個(gè)稱為模的一個(gè)剩余類（也稱同余類），.3. 定義3.（完全剩余系）設(shè)為模的全部剩余類，從每個(gè)中任取一個(gè)元素，得個(gè)數(shù)組成的數(shù)組，叫做模的一個(gè)完全剩余系.例如：關(guān)于模7，下面的每一組數(shù)都是一個(gè)完全剩余系：0，1，2，3，4，5，6；-7，8，16，3，-10，40，20；-3，-2，-1，0，1，2，3。最常用的完全剩余系是最小非負(fù)完全剩余系和絕對(duì)值最小完全剩余系.模的最小非負(fù)完全剩余系是：0，1，2，,;當(dāng)為奇數(shù)時(shí)，絕對(duì)值最

4、小的完全剩余系是：；當(dāng)為偶數(shù)時(shí)，絕對(duì)值最小的完全剩余系有兩個(gè)：；。4.定義4.（簡(jiǎn)化剩余系）在模的完全剩余系中，由所有與互素的數(shù)組成的數(shù)組叫做模的簡(jiǎn)化剩余系，也稱既約剩余系.注意：簡(jiǎn)化剩余系不是完全剩余系，只是完全剩余系的一部分.例如：0、1、2、3、4、5、6、7、8、9是模10的一個(gè)完全剩余系，1、3、7、9是模10的一個(gè)簡(jiǎn)化剩余系，且滿足.5. 歐拉(Euler)函數(shù)個(gè)整數(shù)0,1，中與互素的數(shù)的個(gè)數(shù)，稱之為的歐拉函數(shù)，記為.定理1：若是素?cái)?shù)，則.定理2：若，則.定理3：若的標(biāo)準(zhǔn)分解式是，則的計(jì)算公式是： .例如：； .6.幾條常用的性質(zhì)（1），其中；（2）每一個(gè)整數(shù)只包含于中的一個(gè)里；（

5、3）對(duì)于任意，則的充要條件是.（4）個(gè)整數(shù)構(gòu)成模的一個(gè)完全剩余系任意兩數(shù)模不同余；（5）若是模的一個(gè)完全剩余系，且，則也是模的一個(gè)完全剩余系；（6）簡(jiǎn)化剩余系中數(shù)的個(gè)數(shù)為 ；（7）若是模的一個(gè)簡(jiǎn)化剩余系，且則也是模的一個(gè)簡(jiǎn)化剩余系（其中是歐拉函數(shù)）.【例題分析】1試求被50除所得的余數(shù)。解：由于是關(guān)于的整系數(shù)多項(xiàng)式，而，于是知 又注意到，故又 ，所以 注意到，因而29就是所求的余數(shù).說明：在上述過程中，我們已經(jīng)看到的作用。一般而言，知道一個(gè)整數(shù)的多少次冪關(guān)于模同余于是非常有用的。事實(shí)上，若，則對(duì)大的指數(shù)利用帶余除法定理，可得，于是有，這里余數(shù)是一個(gè)比小得多的數(shù)，這樣一來，計(jì)算的問題，就轉(zhuǎn)化成了

6、計(jì)算余數(shù)次冪的問題，從而使計(jì)算簡(jiǎn)單化。2設(shè)，若今天是星期一，計(jì)算第天后是星期幾？解；星期幾的問題是被7除求余數(shù)的問題.由于，于是，因而。為了把指數(shù)的指數(shù)寫成的形式，還需取6為模來計(jì)算。為此我們有：，進(jìn)而有：， ，依次類推有：，所以 .從而 ，所以星期一后的第天將是星期五.3數(shù)列滿足：證明：（1）對(duì)任意為正整數(shù)； (2)對(duì)任意為完全平方數(shù)。證明：（1）由題設(shè)得且嚴(yán)格單調(diào)遞增.將條件式變形得：兩邊平方整理得-得由式及可知，對(duì)任意為正整數(shù).（2）將兩邊配方，得由式 0（mod 3）為正整數(shù)，式符合題意. 是完全平方數(shù).4求所有的素?cái)?shù)，使得與也是素?cái)?shù)。分析：要使幾個(gè)數(shù)同為質(zhì)數(shù)，一般是利用某一質(zhì)數(shù)的余數(shù)

7、來確定，如均為質(zhì)數(shù)，由于這是的一次式，故三個(gè)數(shù)就用模3的余數(shù)來確定，而二次式對(duì)三個(gè)數(shù)就模5，四個(gè)數(shù)一般就模7了。要使，與都是素?cái)?shù)，須對(duì)除以素?cái)?shù)的余數(shù)進(jìn)行分類討論，最后確定只能是這個(gè)素?cái)?shù).解：設(shè)，且若或4時(shí)，；若或3時(shí)，；即時(shí)，為5的倍數(shù)且比5大，不為質(zhì)數(shù)。故，此時(shí)，；都是素?cái)?shù)，即本題有唯一解。二、幾個(gè)重要定理定理1：（歐拉（Euler）定理）若1，則.證明：取模的一個(gè)既約剩余系 由性質(zhì)易知： 也是模的一個(gè)既約剩余系，于是中的任意一個(gè)數(shù)都能在中找到與它同余的數(shù)，反之也如此從而 ， ，故，證畢.分析： 這是數(shù)論證明題中常用的一種方法，使用一組剩余系，然后乘一個(gè)數(shù)組組成另外一組剩余系來解決問題。定理

8、2：（費(fèi)爾馬（Fermat）小定理）對(duì)于質(zhì)數(shù)及任意整數(shù)有.證明：設(shè)為質(zhì)數(shù)，若是的倍數(shù)，則.若不是的倍數(shù)，則，由歐拉函數(shù)的計(jì)算公式及歐拉定理得，由此定理成立.推論：設(shè)為質(zhì)數(shù)，是與互質(zhì)的任一整數(shù)，則.同余組定義：設(shè)為整系數(shù)多項(xiàng)式（），我們把含有的一組同余式（）稱為同余方程組。特別地，當(dāng)均為的一次整系數(shù)多項(xiàng)式時(shí)，該同余方程組稱為一次同余方程組.若整數(shù)同時(shí)滿足：，則剩余類（其中）稱為同余方程組的一個(gè)解，記作.定理3：（中國剩余定理，也稱孫子定理）設(shè)是兩兩互素的正整數(shù)，那么對(duì)于任意整數(shù)，一次同余方程組，有唯一解：其中 ， 滿足，.【例題分析】【歐拉定理及其應(yīng)用舉例】1.設(shè)，求證：。證明：因?yàn)椋视芍?，?/p>

9、而，但是，故由歐拉定理得：，從而；同理，。于是，即。2、設(shè)求證與的末三位數(shù)相同.證明:由條件只需證明 ，即: 也即證明 事實(shí)上，由 ，利用歐拉定理有 再由是奇數(shù)知: ,進(jìn)而 由(3)、（4），并注意到可得（2），于是（1）成立.【Fetmat小定理及其應(yīng)用舉例】3求證：對(duì)于任意整數(shù)，求證 是整數(shù).證明：令，則只需證是15的倍數(shù)即可。由3，5是素?cái)?shù)及Fetmat小定理得，則，于是有 ；同理 而（3，5）=1，故，即是15的倍數(shù)，所以是整數(shù).4求證：（為任意整數(shù)）。證明：令，則；所以含有因式由Fetmat小定理，知13|7|又13，7，5，3，2兩兩互素，所以2730=能整除。5設(shè)是直角三角形的三

10、邊長(zhǎng)，且都是整數(shù)，求證：可以被30整除。證明：不妨設(shè)是直角三角形的斜邊長(zhǎng)，則。若2 ，2 ，2 c，則，這與 矛盾！所以2|.若3 ，3 ，3 c，因?yàn)椋瑒t，這與矛盾！從而3|.若 5 ，5 ，5 c，因?yàn)椋曰?(mod5)，這與矛盾！從而5|.又(2,3,5)=1，所以30|.【中國剩余定理應(yīng)用舉例】6證明：對(duì)于任意給定的正整數(shù)，均有連續(xù)個(gè)正整數(shù)，其中每一個(gè)都有大于1的平方因子。證明：由于素?cái)?shù)有無窮多個(gè)，故我們可以取個(gè)互不相同的素?cái)?shù)，而考慮同余組 因?yàn)轱@然是兩兩互素的，故由中國剩余定理知，上述同余組有正整數(shù)解。于是，連續(xù)個(gè)數(shù)分別被平方數(shù)整除。注：本題的解法體現(xiàn)了中國剩余定理的一個(gè)基本功效，它常常能將“找連續(xù)個(gè)正整數(shù)具有某種性質(zhì)”的問題轉(zhuǎn)化為“找個(gè)兩兩互素的數(shù)具有某種性質(zhì)”，而后者往往是比較容易解決的。7證明：對(duì)于任意給定的正整數(shù)，均有連續(xù)個(gè)正整數(shù)，其中每一個(gè)都不是冪數(shù)。分析：我們來證明，存在連續(xù)個(gè)正整數(shù)，其中每一個(gè)數(shù)都至少有一個(gè)素因子，在這個(gè)數(shù)的標(biāo)準(zhǔn)分解中僅出現(xiàn)一次，從而這個(gè)數(shù)不是冪數(shù)。證明：取個(gè)互不相同的素?cái)?shù)，考慮同余組.因?yàn)椋@然是兩兩互素的，故由中國剩余定理知，上述同余組有正整數(shù)解，.同理知，同余組有整數(shù)解，即，故 ，即在的標(biāo)準(zhǔn)分解中恰好出現(xiàn)一次，所以 都不是冪數(shù).8