高中數(shù)學(xué)奧賽輔導(dǎo)第三講同余

1、數(shù)學(xué)奧賽輔導(dǎo) 第三講 同余知識、方法、技能同余是數(shù)論中的重要概念，同余理論是研究整數(shù)問題的重要工作之一.本講介紹同余的基本概念，剩余類和完全剩余系，同余方程，整數(shù)模的階和中國剩余定理.基本概念定義一：設(shè)m是一個(gè)給定的正整數(shù).如果兩個(gè)整數(shù)a、b用m除所得的余數(shù)相同，則稱a、b對模m同余，記為ab（modm）；否則，記為ab（modm）.例如，157（mod4），2312（mod7）.同余有如下兩種等價(jià)定義法：定義一* 若m|ab，則稱a、b對模m同余.定義一*若a=b+mt(tZ)，則稱a、b對模m同余.同余的基本性質(zhì)：（1）（2） （3）若（4）若特別地，設(shè)，則（5）若特別地，又若（c,m）=

2、1，則【證明】因這等價(jià)于又因若（a,b）=1（d0）及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è)mN*，把全體整數(shù)按其對模m的余數(shù)r（0rm1）歸于一類，記為kr，每一類kr（r=0,1,m1）均稱模m的剩余類（又叫同余類）.同一類中任一數(shù)稱為該類中另一數(shù)的剩余.剩余類kr是數(shù)集,它是一個(gè)公差為m的（雙邊無窮）等差數(shù)列.根

3、據(jù)定義，剩余類具有如下性質(zhì)：（1）（2）對任一數(shù)nZ，有惟一的；（3）對任意的a,bZ，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，m1；（2）絕對值最小完全剩余系：它隨m的奇偶性不同而略有區(qū)別.當(dāng)（對稱式）當(dāng)由定義不難得到如下判別完全剩余系的方法：定理一：m個(gè)整數(shù)是模m的

4、一個(gè)完系定理二：設(shè)（b,m）=1，c為任意整數(shù).若為一個(gè)完系，則也是模m的一個(gè)完全剩余系.特別地，任意m個(gè)連續(xù)整數(shù)構(gòu)成模m的一個(gè)完全剩余系.【證明】只需證明：當(dāng)而這可用反證法得證.下略.設(shè)m為一正整數(shù)，由于在0，1，m1中與m互質(zhì)的數(shù)的個(gè)數(shù)是由m惟一確定的一個(gè)正整數(shù)，因此，可給出如下定義.定義四：m為一正整數(shù)，把0，1，m1與m互質(zhì)的數(shù)的個(gè)數(shù)叫做m的歐拉函數(shù)，記為顯然，的定義域是正整數(shù)N*，前n個(gè)值為：當(dāng)m=p為質(zhì)數(shù)時(shí)，設(shè)k是模的一個(gè)剩余類.若a、bk，則于是由性質(zhì)9知，（a,m）=（b,m）.因此，若（a,m）=1，則k中的任一數(shù)均與m互質(zhì).這樣，又可給出如下定義.定義五：如果一個(gè)模m的剩余

5、類kr中任一數(shù)與m互質(zhì)，則稱kr是與模m互質(zhì)的剩余類；在與模m互質(zhì)的每個(gè)剩余類中任取一個(gè)數(shù)（共個(gè)）所組成的數(shù)組，稱為模m的一個(gè)簡化剩余系.例如，取m=6，在模6的六個(gè)剩余類中，是與模6互質(zhì)的剩余類.數(shù)組1，5；7，7；1，1；等等都是模6的簡化剩余類.由此定義，不難得到：定理三:是模m的簡化剩余系定理四：在模m的一個(gè)完全剩余系中，取出所有與m互質(zhì)的數(shù)組成的數(shù)組，就是一個(gè)模m的簡化剩余系.這兩個(gè)定理，前者是簡化剩余系的判別方法，后者是它的構(gòu)造方法.顯然，模m的簡化剩余系有無窮多個(gè)，但常用的是“最小簡化剩余系”，即由1，2，m1中與m互質(zhì)的那些數(shù)組成的數(shù)組.由定理不難證得簡化剩余系的如下性質(zhì)定理.

6、定理五：設(shè)是模m的簡化剩余系.若（k,m）=1，則也是模m的簡化剩余系.下面介紹兩個(gè)有關(guān)歐拉函數(shù)的重要結(jié)論.其證明略.定理六：（歐拉定理）若（a,m）=1，則特別地，（費(fèi)馬小定理）若m=p為質(zhì)數(shù)，p a，則定理七：（威爾遜定理）設(shè)p素?cái)?shù)，則（p1）！定理八：（歐拉函數(shù)值計(jì)算公式）令m的標(biāo)準(zhǔn)分解式為 ，則 例如，30=2·3·5，則讀者應(yīng)認(rèn)識到：由于任何整數(shù)都屬于模m的某一剩余類，所以，在研究某些整數(shù)性質(zhì)時(shí)，選取適當(dāng)?shù)模＃﹎，然后在模m的每個(gè)剩余類中取一個(gè)“代表數(shù)”（即組成一個(gè)完全剩余系），當(dāng)弄清了這些代表數(shù)的性質(zhì)后，就可弄清對應(yīng)的剩余類中所有數(shù)的性質(zhì)，進(jìn)而弄清全體整數(shù)的性

7、質(zhì)，這就是引入剩余類和完全剩余系的目的.同余方程設(shè)的整系數(shù)多項(xiàng)式.類似于多項(xiàng)式和代數(shù)方程式的有關(guān)定義，我們有定義六：同余式叫做一元n次同余方程.例如，是七次同余方程.定義七：若c使得叫做同余方程的一個(gè)解.顯然，同余方程的解是一些剩余類，而不僅是一個(gè)或n個(gè)類.例如，都是二次同余方程的解.1一次同余方程（其中m a）稱為一次同余方程.關(guān)于它的解，有如下共知的結(jié)論：定理九：若（a,m）=1，則有一個(gè)解.定理十：若（a,m）=d>1，d b，則無解，其中.定理十一：若（a,m）=d>1，d|b，則有d個(gè)解.并且，若的一個(gè)解為則d個(gè)解為：，其中 下面介紹一次同余方程 （*）的解法.【解法1】

8、因（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，1km，使得.我們將具有這一性質(zhì)的最小

9、正整數(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的階整除p1.（2）中國剩余定理（即孫子定理）設(shè)是兩兩互質(zhì)的正整數(shù)，記M=則同余方程組 有且只有解 （）其中 （）【證明】由知，因此每一個(gè)同余方程（i=1，2，n）都有解，于是必存在所以對模故（）是（）的解.若是適合（）的任意兩個(gè)解，則故因此，（）是（）的惟一解.賽題精講例

10、1：數(shù)1978n與1978m的最末三位數(shù)相等，試求正整數(shù)m和n，使得n+m取最小值，這里 （第20屆IMO試題）【解】由已知1000=8×125，所以 因，且（1978m，125）=1，則由式知1978nm1（mod125）又直接驗(yàn)證知，1978的各次方冪的個(gè)位數(shù)字是以8、4、2、6循環(huán)出現(xiàn)的，所以只有nm為4的倍數(shù)時(shí)，式才能成立，因而可令nm=4k.由于. n+m=（ nm）+2m=4k+2m，因而只需確定出k和m的最小值.先確定k的最小值：因?yàn)?9784=（79×25+3）4341（mod5），19784341（mod25）.故可令19784=5t+1，而5 t，從而0

11、1978nm1=19784k1=（5k+1）k1+，顯然，使上式成立的k的最小值為25.再確定m的最小值：因19782（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（m2，mN*）后的余數(shù)組成數(shù)列.若是一個(gè)周期數(shù)列，則稱是關(guān)于模m的周期數(shù)列，簡稱模m周期數(shù)列.滿足（或（modm）的最小正整數(shù)T稱為它的周期.例如，（1）是模10周期數(shù)

12、列，周期為4；（2）自然數(shù)列n是一個(gè)模m（m2，mN*）周期數(shù)列，周期為m；（3）任何一個(gè)整數(shù)等差數(shù)列都是一個(gè)模m（m2，mN*）周期數(shù)列，周期為m.例2：設(shè)a是方程的最大正根，求證：17可以整除a1788與a1988.其中x表示不超過x的最大整數(shù). （第29屆IMO預(yù)選題）【證明】根據(jù)如下符號表可知，若設(shè)三根依次為，則x113f(x)符號+另一方面，由韋達(dá)定理知，為了估計(jì)、，先一般考察an，為此定義：直接計(jì)算可知：又因當(dāng)時(shí)，由此知，命題變?yōu)樽C明：能被17整除.現(xiàn)考察在模17的意義下的情況：可見，在模17意義下，是16為周期的模周期數(shù)列，即由于1788故命題得證.例3：求八個(gè)整數(shù)滿足：對每個(gè)整

13、數(shù)k（1985<k<1985），有八個(gè)整數(shù)a1，a2，a81，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，n1，給M中每個(gè)數(shù)染上黑、白兩種顏色中的一種，染法如下：（i

14、）對M中每個(gè)i，i與ni同色；（ii）對M中每個(gè)i，ik,i與|ki|同色.求證：M中所有的數(shù)必為同色. （第26屆IMO試題）【證明】因又0，1，n1是模n的一個(gè)完全剩余系，所以0，k，2k，（n1）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ù)，證明：2p1的任一素因了具有形式是正整數(shù).【證明】設(shè)q是2p

15、1的任一素因子，則q2.設(shè)2模q的階是k，則由知k|p，故k=1或p（因p是素?cái)?shù)，這是能確定階k的主要因素）.顯然k1，否則這不可能，因此k=p.現(xiàn)在由費(fèi)馬小定理推出因p、q都是奇數(shù)，故q1=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（n1）是偶數(shù).證明：存在是【證明】我們先證明，當(dāng)n為素?cái)?shù)冪時(shí)結(jié)論成立.實(shí)際上，我們能證明，存在x,y，使p xy，且.如p=2，則條件表明k為偶數(shù)，可取中有一對滿足要求.一般情形下，設(shè)是n的標(biāo)準(zhǔn)分解，上面已證明，對每個(gè)，均有整數(shù)，使pi xi