Http://www.fhedu.cPAGEPAGE4網(wǎng)站地址：南京市湖南路1號B座808室聯(lián)系電話/p>

Mail：admin@【高中數(shù)學(xué)奧賽金牌之路精華教案】數(shù)學(xué)奧賽輔導(dǎo)第三講同余知識、方法、技能同余是數(shù)論中的重要概念，同余理論是研究整數(shù)問題的重要工作之一.本講介紹同余的基本概念，剩余類和完全剩余系，同余方程，整數(shù)模的階和中國剩余定理.Ⅰ.基本概念定義一：設(shè)m是一個(gè)給定的正整數(shù).如果兩個(gè)整數(shù)a、b用m除所得的余數(shù)相同，則稱a、b對模m同余，記為a≡b（modm）；否則，記為a≡b（modm）.例如，15≡7（mod4），－23≡12（mod7）.同余有如下兩種等價(jià)定義法：定義一*若m|a－b，則稱a、b對模m同余.定義一**若a=b+mt(t∈Z)，則稱a、b對模m同余.同余的基本性質(zhì)：（1）（2）（3）若①②（4）若特別地，設(shè)，則（5）若特別地，又若（c,m）=1，則【證明】因這等價(jià)于又因若（a,b）==1（d≠0）及b|ac，且（b,c）=1從而有這個(gè)性質(zhì)說明同余式兩邊的同一非零因數(shù)，不能像等式那樣“約去”，只有當(dāng)這非零因數(shù)與?；ベ|(zhì)時(shí)，才可“約去”.（6）而（7）設(shè)①若c>0，則②d為a、b、m的任一公約數(shù)，則（8）若（9）若Ⅱ.剩余類和完全剩余系若按對某一模m的余數(shù)進(jìn)行分類，就可以引入所謂的剩余類和完全剩余系的概念.定義二：設(shè)m∈N*，把全體整數(shù)按其對模m的余數(shù)r（0≤r≤m－1）歸于一類，記為kr，每一類kr（r=0,1,…,m－1）均稱模m的剩余類（又叫同余類）.同一類中任一數(shù)稱為該類中另一數(shù)的剩余.剩余類kr是數(shù)集,它是一個(gè)公差為m的（雙邊無窮）等差數(shù)列.根據(jù)定義，剩余類具有如下性質(zhì)：（1）（2）對任一數(shù)n∈Z，有惟一的；（3）對任意的a,b∈Z，a,b定義三：設(shè)是模m的（全部）剩余類.從每個(gè)kr中任取一個(gè)數(shù)ar,這m個(gè)數(shù)組成的一個(gè)組稱為模m的一個(gè)完全剩余系，簡稱完系.例如，取m=4，則有，k2={…，－6，－2，2，6，10，…}，k3={…，－5，－1，3，7，11，…}.數(shù)組0，1，2，3；－8，5，2，－1等等都是模的4的一個(gè)完全剩余系.顯然，模m的完全剩余系有無窮多個(gè).但最常用的是下面兩種：（1）非負(fù)數(shù)最小完全剩余系：0，1，2，…，m－1；（2）絕對值最小完全剩余系：它隨m的奇偶性不同而略有區(qū)別.（其中ma）稱為一次同余方程.關(guān)于它的解，有如下共知的結(jié)論：定理九：若（a,m）=1，則有一個(gè)解.定理十：若（a,m）=d>1，db，則無解，其中.定理十一：若（a,m）=d>1，d|b，則有d個(gè)解.并且，若的一個(gè)解為則d個(gè)解為：，其中下面介紹一次同余方程（*）的解法.【解法1】因（a,m）=1，則存在二數(shù)s,t，使得as+mt=1，即，由此有為（*）的解.【解法2】先把（*）變形成僅只是形式上的記號），然后用與m互質(zhì)的數(shù)陸續(xù)乘右端的分子分母，直至把分母絕對值變成1（通過分子分母各對模m取余數(shù)）而得到解.【解法3】得用歐拉定理.因從而有解2．一次同余方程組定義八：若數(shù)r同時(shí)滿足n個(gè)同余方程：叫做這n個(gè)同余方程組成的同余方程組的解.定理十二：對同余方程組記①若d，則此同余方程組無解；②若，則此同余方程組有對模M的一類剩余解.Ⅳ.模m的階和中國剩余定理（1）模m的階定義九：設(shè)m>1是一個(gè)固定的整數(shù)，a是與m互素的整數(shù)，則存在整數(shù)k，1≤k＜m，使得.我們將具有這一性質(zhì)的最小正整數(shù)（仍記為k）稱為a模m的階.a模m的階具有如下性質(zhì)：①設(shè)的階，是任意整數(shù)，則的充要條件是.特別地，的充分必要條件是k|u.【簡證】充分性顯然.必要性.設(shè)用帶余除法，及k的定義知，必須r=0，所以②設(shè)模m的階為k，則數(shù)列模m是周期的，且最小正周期是k，而k個(gè)數(shù)模m互不同余.③設(shè)模m的階整除歐拉函數(shù)特別地，若m是素?cái)?shù)p，則a模p的階整除p－1.（2）中國剩余定理（即孫子定理）設(shè)是兩兩互質(zhì)的正整數(shù)，記M=則同余方程組有且只有解（△）其中（△△）【證明】由知，，因此每一個(gè)同余方程（i=1，2，…n）都有解，于是必存在所以對模故（△△）是（△）的解.若是適合（△）的任意兩個(gè)解，則故因此，（△△）是（△）的惟一解.賽題精講例1：數(shù)1978n與1978m的最末三位數(shù)相等，試求正整數(shù)m和n，使得n+m取最小值，這里（第20屆IMO試題）【解】由已知1000=8×125，所以①②因，且（1978m，125）=1，則由②式知1978n－m≡1（mod125）③又直接驗(yàn)證知，1978的各次方冪的個(gè)位數(shù)字是以8、4、2、6循環(huán)出現(xiàn)的，所以只有n－m為4的倍數(shù)時(shí)，③式才能成立，因而可令n－m=4k.由于.n+m=（n－m）+2m=4k+2m，因而只需確定出k和m的最小值.先確定k的最小值：因?yàn)?9784=（79×25+3）4≡34≡1（mod5），19784≡34≡1（mod25）.故可令19784=5t+1，而5t，從而0≡1978n－m－1=19784k－1=（5k+1）k－1≡+，顯然，使上式成立的k的最小值為25.再確定m的最小值：因1978≡2（mod8），則由①式知，④由于④式顯然對m=1，2不成立，從而m的最小值為3.故合于題設(shè)條件的n+m的最小值為106.【評述】比例中我們用了這樣一個(gè)結(jié)論：1978的各次方冪的個(gè)位數(shù)字是以8，4，2，6循環(huán)出現(xiàn)，即，當(dāng)r=1，2，3，4時(shí)，這種現(xiàn)象在數(shù)學(xué)上稱為“模同期現(xiàn)象”.一般地，我們有如下定義：整數(shù)列各項(xiàng)除以m（m≥2，m∈N*）后的余數(shù)組成數(shù)列.若是一個(gè)周期數(shù)列，則稱是關(guān)于模m的周期數(shù)列，簡稱模m周期數(shù)列.滿足（或（modm））的最小正整數(shù)T稱為它的周期.例如，（1）是模10周期數(shù)列，周期為4；（2）自然數(shù)列{n}是一個(gè)模m（m≥2，m∈N*）周期數(shù)列，周期為m；（3）任何一個(gè)整數(shù)等差數(shù)列都是一個(gè)模m（m≥2，m∈N*）周期數(shù)列，周期為m.例2：設(shè)a是方程的最大正根，求證：17可以整除[a1788]與[a1988].其中[x]表示不超過x的最大整數(shù).（第29屆IMO預(yù)選題）【證明】根據(jù)如下符號表可知，若設(shè)三根依次為，則x－1－13f(x)符號－++－－+另一方面，由韋達(dá)定理知，為了估計(jì)[]、[]，先一般考察[an]，為此定義：直接計(jì)算可知：又因當(dāng)時(shí)，由此知，命題變?yōu)樽C明：能被17整除.現(xiàn)考察在模17的意義下的情況：可見，在模17意義下，是16為周期的模周期數(shù)列，即由于1788故命題得證.例3：求八個(gè)整數(shù)滿足：對每個(gè)整數(shù)k（－1985<k<1985），有八個(gè)整數(shù)a1，a2，…，a8∈{－1，0，1}，使得（第26屆IMO預(yù)選題）【解】令數(shù)集記顯然H，記且G中的元素個(gè)數(shù)有個(gè).又因G中任意兩數(shù)之差的絕對值不超過2H，所以G中的數(shù)對模2H+1不同余.因此，G的元素恰好是模2H+1的一個(gè)絕對值最小的完系，于是，凡滿足的任意整數(shù)都屬于G，且可惟一地表示為：形式.當(dāng)n=7時(shí)，H=3280>1985，而n=6時(shí)，H=1043<1985.故n1=1，n2=3，…，n8=37為所求.例4：設(shè)n為正整數(shù)，整數(shù)k與n互質(zhì)，且0<k<n.令M={1，2，…，n－1}，給M中每個(gè)數(shù)染上黑、白兩種顏色中的一種，染法如下：（i）對M中每個(gè)i，i與n－i同色；（ii）對M中每個(gè)i，i≠k,i與|k－i|同色.求證：M中所有的數(shù)必為同色.（第26屆IMO試題）【證明】因又0，1，…n－1是模n的一個(gè)完全剩余系，所以0，k，2k，…，（n－1）k也是模n的一個(gè)完全剩余系.若設(shè)則M=下只需證因?yàn)椋羧绱?，?dāng)r1的顏色確定后，M中所有都與r1同色.由于，因此，（1）若，于是，由條件（i）知，同色.又由條件（ii）知，同色，故同色.綜上所述可知，同色.命題得證.例5：設(shè)a和m都是正整數(shù)，a>1.證明：【證明】實(shí)上，顯然互素，且的階是m，所以由模階的性質(zhì)③導(dǎo)出例6：設(shè)p是奇素?cái)?shù)，證明：2p－1的任一素因了具有形式是正整數(shù).【證明】設(shè)q是2p－1的任一素因子，則q≠2.設(shè)2模q的階是k，則由知k|p，故k=1或p（因p是素?cái)?shù)，這是能確定階k的主要因素）.顯然k≠1，否則這不可能，因此k=p.現(xiàn)在由費(fèi)馬小定理推出因p、q都是奇數(shù)，故q－1=2px（x是個(gè)正整數(shù)），證畢.例7：設(shè)m,a,b都是正整數(shù)，m>1，則【證明】記由于（a,b）|a及（a,b）|b，易知及，故，另一方面設(shè)m模d的階是k，則由推出，k|a及k|b，故k|（a，b）.因此綜合兩方面可知，證畢.例8：設(shè)n，k是給定的整數(shù)，n>0，且k（n－1）是偶數(shù).證明：存在是【證明】我們先證明，當(dāng)n為素?cái)?shù)冪時(shí)結(jié)論成立.實(shí)際上，我們能證明，存在x,y，使pxy，且.如p=2，則條件表明k為偶數(shù)，可取中有一對滿足要求.一般情形下，設(shè)是n的標(biāo)準(zhǔn)分解，上面已證明，對每個(gè)，均有整數(shù)，，使pixiyi，且現(xiàn)在孫子定理表明，同余方程組有解x，同樣也有解y.現(xiàn)在易證x,y符合問題中的要求：因pixiyi，故pixy（i=1，…，r），于是（