基礎(chǔ)知識(shí)——數(shù)論函數(shù)中同余

1、同余式性質(zhì)應(yīng)用非常廣泛， 面的問題中有著不可替代的功能, 國剩余定理。同余在處理某些整除性、進(jìn)位制、對(duì)整數(shù)分類、解不定方程等方與之密切相關(guān)的的數(shù)論定理有歐拉定理、費(fèi)爾馬定理和中基礎(chǔ)知識(shí)三個(gè)數(shù)論函數(shù)對(duì)于任何正整數(shù)均有定義的函數(shù),稱為數(shù)論函數(shù)。在初等數(shù)論中，所能用到的無非也就有三個(gè)，分別為：高斯（Gauss）取整函數(shù)x及其性質(zhì)，除數(shù)函數(shù)d（ n）和歐拉（Euler）函數(shù)（x）和 它的計(jì)算公式。1 .高斯（Gauss）取整函數(shù)x 設(shè)x是實(shí)數(shù)，不大于x的最大整數(shù)稱為x的整數(shù)部分，記為x；x x稱為x的小數(shù)部分,記為 x o 例如：0.5 =0, J50 7, 33, 4, 0,1415 , 0.3 0

2、.7等等。由x,x的定義可得如下性質(zhì):性質(zhì)1. x x x;0 x 1;性質(zhì)2. x 1 x x x 1 ;性質(zhì)3. 設(shè)a Z ,則a x a x；性質(zhì)4. x y x y; x y x y；x性質(zhì)5. x L jx 1性質(zhì)6.對(duì)于任意的正整數(shù)1x x - x nn ,都有如下的埃米特恒等式成立:2 n為了描述性質(zhì)7,我們給出如下記號(hào)：若 b |a,且b 1|a,則稱為b恰好整除a ,記為的整數(shù)a能唯一地寫成ap1al p；2b |a o例如：我們有24|2000,53|2000等等，其實(shí)，由整數(shù)唯一分解定理：任何大于1p：k ,i 1,2, ,k的形式，其中 Pi為質(zhì)（素）數(shù)（Pipj（i

3、j）。我們還可以得到:Piai |a,i1,2, ,k。性質(zhì) 7.若 p |n!,則口 三P P請(qǐng)注意，此式雖然被寫成了無限的形式，但實(shí)際上對(duì)于固定的n,必存在正整數(shù)k ,使得pk n,因而0 pk 1,故二0,而且對(duì)于m k時(shí)，都有二0。因此， PP上式實(shí)際上是有限項(xiàng)的和。另外，此式也指出了乘數(shù) n!的標(biāo)準(zhǔn)分解式中，素因數(shù)p的指數(shù)的計(jì)算方法。2 .除數(shù)函數(shù)d(n)正整數(shù)n的正因數(shù)的個(gè)數(shù)稱為除數(shù)函數(shù)，記為 d( n)。這里給出d( n)的計(jì)算公式：d(n) = ( i 1)( 2 1)( ki), i, 2, k i為素?cái)?shù)唯一分解定理中的指數(shù)。為了敘述地更加明確，我們組出素?cái)?shù)唯一分解定理。算術(shù)

4、基本定理(素?cái)?shù)唯一分解定理)：任何一大于1的整數(shù)均可以分解為素?cái)?shù)的乘積，若不考慮素?cái)?shù)乘積的先后順序，則分解式是唯一的。例如：24 2 2 2 3。當(dāng)一個(gè)整數(shù)分解成素?cái)?shù)的乘積時(shí)，其中有些素?cái)?shù)可以重復(fù)出現(xiàn)。例如在上面的分解式中，2出現(xiàn)了三次。把分解式中相同的素?cái)?shù)的積寫成哥的形式，我們就可以把大于1的正整數(shù)a寫成a pp；2p：k,i 1,2, ,k (1)此式稱為a的標(biāo)準(zhǔn)分解式。這樣，算術(shù)基本定理也可以描述為大于1的整數(shù)的標(biāo)準(zhǔn)分解式是唯一的(不考慮乘積的先后順序)。推論1.若a的標(biāo)準(zhǔn)分解式是(1)式，則d是a的正因數(shù)的充要條件是：d R、2 pJ,。 i ai,i 1,2, ,k(2)應(yīng)說明(2)

5、不能稱為是d的標(biāo)準(zhǔn)分解式，其原因是其中的某些i可能取零值(d也有可能不含有某個(gè)素因數(shù) pi,因而i 0)推論2.設(shè)a bc,且(b,c) 1 ,若a是整數(shù)的k次方，則b,c也是整數(shù)的k次方。特另U地，若a是整數(shù)的平方，則b,c也是整數(shù)的平方。3 .歐拉(Euler)函數(shù) (n)設(shè)n正整數(shù)0,1 ,n 1中與n互素的個(gè)數(shù)，稱之為n的歐拉函數(shù)，并記為 (n)。若n的標(biāo)準(zhǔn)分解式是n p；1 p；2p：k,i 1,2, ,k，則(n)的計(jì)算公式是：(n) p；1 1 p；2 1 pak 1(p1 1)( p2 1) (pk 1),i 1,2, ,k例如：(2000)(2453) 2453(2 1)(5

6、 1) 800；(2001)(3 23 29) (3 1)(23 1)(29 1) 1432.以下我們講述同余的概念:同余的概念是高斯(Gauss)在1800年左右給出的。設(shè)m是正整數(shù)，若用m去除整數(shù)a,b, 所得的余數(shù)相同，則稱為 a與b關(guān)于模m同余，記作a b(modm),否則，稱為a與b關(guān) 于模m不同余。定義1.(同余)設(shè)m 0,若m | (a b),則稱a和b對(duì)*m m同余，記作a b(mod m)； 若不然，則稱 a和b對(duì)*m m不同余，記作 a b(mod m)。例如： 34 4(mod15), 10001(mod7)等等。當(dāng)0 b m時(shí)，a b(mod m),則稱b是a對(duì)*m m

7、的最小非負(fù)剩余。由帶余除法可知， a和b對(duì)卞m同余的充要條件是 a與b被m除得的余數(shù)相同。對(duì)于 固定的模m ,模m的同余式與通常的等式有許多類似的性質(zhì)：性質(zhì)1. a b(mod m)的充要條件是 a b mt,t Z也即m | (a b)。性質(zhì)2.同余關(guān)系滿足以下規(guī)律：(1)(反身性) a a(mod m)；(2)(對(duì)稱性)若 a b(mod m),則 b a(mod m)；(3)(傳遞性)若 a b(mod m) , b c(mod m),則 a c(mod m)；(4)(同余式相加)若ab(mod m) , cd(mod m),則 ac b d(modm)；(5)(同余式相乘)若ab(mo

8、d m) , cd(mod m),貝U acbd(modm)；反復(fù)利用(4) (5),可以對(duì)多個(gè)兩個(gè)的(模相同的)同余式建立加、減和乘法的運(yùn)算公式。特別地，由(5)易推出：若a b(mod m) , k, c為整數(shù)且k 0,則akc bkc(mod m)；但是同余式的消去律一般并不成立，即從 ac bc(mod m)未必能推出a b(mod m),可是我們卻有以下結(jié)果：(6)若ac bc(modm),則a b mod m ,由此可以推出，若 (c,m) 1,則有 (m,c)a b(mod m),即在c與m互素時(shí)，可以在原同余式兩邊約去c而不改變模(這一點(diǎn)再一次說明了互素的重要性)?，F(xiàn)在提及幾個(gè)

9、與模相關(guān)的簡(jiǎn)單而有用的性質(zhì)：(7)若 a b(mod m) , d I m ,則 a b(mod d);(8)若 a b(mod m) , d 0 ,貝U da db(mod dm)；(9)若 a b(modF )(i 1,2, ,k),則 a b(modm1,m2, ,mn),特別地，若 叫血，n兩兩互素時(shí)，則有 a b(modm1m2 mn);kkkk性質(zhì) 3.若 ai bi (mod m),i 1,2, ,k，則 aj R (mod m) ；ajR ;i 1i 1i 1i 1性質(zhì)4.設(shè)f(x)是系數(shù)全為整數(shù)的多項(xiàng)式，若 a b(modm),則f(a) f(b)(modm)。這一性質(zhì)在計(jì)算

10、時(shí)特別有用：在計(jì)算大數(shù)字的式子時(shí)，可以改變成與它同余的小的數(shù)字，使計(jì)算大大地簡(jiǎn)化。如例 3。定義2.設(shè)(a,m) 1, d0是使ad 1(mod m)成立的最小正整，則稱 d0為a對(duì)*H m的階。在取定某數(shù) m后，按照同余關(guān)系把彼此同余的整數(shù)歸為一類，這些數(shù)稱為模m的剩余類。一個(gè)類的任何一個(gè)數(shù)，都稱為該類所有數(shù)的剩余。顯然，同類的余數(shù)相同，不同類的余數(shù)不相同，這樣我們就把全體整數(shù)按照模 m劃分為了 m個(gè)剩余類：Kr qm r |q Z,0 余數(shù)r m 1。在上述的m個(gè)剩余類中，每一類任意取一個(gè)剩余，可以得到m個(gè)數(shù)a。，“， ,am 1,稱為模m的一個(gè)完全剩余系。例如關(guān)系模7,下面的 每一組數(shù)都

11、是一個(gè)完全剩余系：0, 1, 2, 3, 4, 5, 6;-7 , 8, 16, 3, -10 , 40, 20;-3 , -2 , -1 , 0, 1, 2, 3。顯然，一組整數(shù)成為模 m的完全剩余系只需要滿足兩個(gè)條件(1)有m個(gè)數(shù)；(2)各數(shù)關(guān)于模m兩兩不同余。最常用的完全剩余系是最小非負(fù)完全剩余系及絕對(duì)值最小完全剩余系。模m的最小非負(fù)完全剩余系是：0, 1, 2, ,m 1;即除數(shù)為m時(shí)，余數(shù)可能取到的數(shù)的全部值。m 1m 1當(dāng)m為奇數(shù)時(shí)，絕對(duì)值最小的完全剩余系是：m，,1,0,1, ,m；221, , 1,0,1,;2m /,1,0,1, 1。2為了方便大家研究，我們把有關(guān)材料上的具體

12、概,x r(mod m), r 0,1, ,m 1,每一個(gè)這樣的類當(dāng)m為偶數(shù)時(shí)，絕對(duì)值最小的完全剩余系有兩個(gè)： m2m2 , 以上只是我們個(gè)人對(duì)同余及剩余類的理解， 念給出，希望大家好好地研究：定義3.(同余類)設(shè)M r x | x Z為模m的同余類。說明：整數(shù)集合可以按模 m來分類，確切地說，若 a和b模m同余，則a和b屬同一類，否則不屬于同一類，每一個(gè)這樣的類為模 m的一個(gè)同余類。由帶余除法，任一整數(shù)必恰與0,1,m 1中的一個(gè)模 m同余，而0,1,m 1這m個(gè)數(shù)彼此模 m不同余,因此模m共有m個(gè)不同的同余類，即 Mr x|x Z,x r(mod m), r 0,1, ,m 1。例如，模2

13、的同余類共有兩個(gè)，即通常說的偶數(shù)類與奇數(shù)類，這兩類中的數(shù)分別具有形式 2k和2k 1 (k為任意整數(shù))。定義4。(剩余類)設(shè) m是正整數(shù)，把全體整按對(duì)模 m的余數(shù)分成 m類，相應(yīng)的m個(gè)集合 記為：K0, K1, , Km 1,其中Kr qm r | q Z,0 余數(shù)r m 1,稱為模m的一個(gè) 剩余類。以下是幾條常用性質(zhì)：(1) ZKi 且 Ki Kj (i j)；0 i m 1(2)每一個(gè)整數(shù)僅在 Ko,K1, ,Km1的一個(gè)里；(3)對(duì)于任意a,b Z ,則a, b Kr的充要條件是a b(mod m)。定義5.(完全剩余系)一組數(shù) y1,y2, ,ys稱為模m的完全剩余系，如果對(duì)任意 a有

14、且僅有一個(gè)yj是a對(duì)*m m的剩余，即a yj (mod m)。換一種說法更好理解：設(shè)&,Ki, ,Km1為模m的全部剩余類，從每個(gè)Kr中任取一個(gè)a,，得m個(gè)數(shù)%同，am1組 成的數(shù)組，叫做模 m的一個(gè)完全剩余系。說明：在m個(gè)剩余類中各任取一個(gè)數(shù)作為代表，這樣的m個(gè)數(shù)稱為模 m的一個(gè)完全剩余系，簡(jiǎn)稱模 m的完系。換句話說，m個(gè)數(shù)g,c2, ,cm稱為模m的一個(gè)完系，是指它們彼此模m不同余，例如 0,1, 2, , m 1是模m的一個(gè)完系，這稱作是模m的最小非負(fù)完系。兩兩對(duì)模不同余;性質(zhì)：(1) m個(gè)整數(shù)卞成模 m的一個(gè)完全剩余系(2)若(a,m) 1,則x與ax b同時(shí)跑遍模 m的完全

15、剩余系。典例分析例1 .試解方程:5 6x 15x 785解：因?yàn)樽筮吺钦麛?shù)，因而右邊的分式也應(yīng)該是整數(shù)，所以曰 81 90x405 6x 15x 78515x 755 6x8一一 81 90x-0,從而 01,故 0 81 90x 40。40,115x 7 一但是15x 7是整數(shù)，故15x 5t 7 , t Z ,代入前面的不等式，得 57 40 39 30t 40,t Z ,直接觀察即知t 0,1 ,于是x ,一。15 5例2.數(shù)100!的十進(jìn)位制表示中，未尾連續(xù)地有多少位全是零？解：命題等價(jià)于100!最多可以被10的多少次方整除。因?yàn)?10 2 5因而100!中2的指 數(shù)大于5的指數(shù)，所

16、以100!中5的指數(shù)就是所需求出的零的位數(shù)。由竺0”020 4 24即可知100!的未尾連續(xù)地有 24位全是數(shù)碼零。552例3.試求(25733 46)26被50除所得的余數(shù)。解：由于(x33 46)26是關(guān)于x的整系數(shù)多項(xiàng)式，而 257 7(mod50),于是知3326,_,3326 .(25746)(746) (mod 50)。又注意到 72 491(mod50),故(25746)(746) (mod50) (72)16 7 46)(1)16 7 46)26 (7 46)26 5326 326(mod 50)又 35 243 250 7 7(mod 50),所以(25733 46)26 (

17、35)5 3 ( 7)5 3(72)2 7 321 29(mod 50)注意到0 29 50,因而29就是所求的余數(shù)。說明：在上述過程中，我們已經(jīng)看到72 491(mod50)的作用。一般而言，知道一個(gè)整數(shù)的多少次哥關(guān)于模同余于1是非常有用的。事實(shí)上，若ak 1(mod m),則對(duì)大的指數(shù)n利用帶余除法定理， 可得n kq r,0 r k ,于是有an akq r (ak)qar ar(mod m), 這里余數(shù)r是一個(gè)比n小得多的數(shù)，這樣一來，計(jì)算an的問題，就轉(zhuǎn)化成了計(jì)算余數(shù)r次哥ar的問題，從而使計(jì)算簡(jiǎn)單化。 10例4.設(shè)a 1010，計(jì)算某星期一后的第 a天是6星期幾？解；星期幾的問題是

18、被 7除求余數(shù)的問題。由于10 3(mod 7),于是102 32 2(mod 7), 103 33 2 3 6 1(mod 7),因而 106 1(mod 7)。為了把指數(shù)a的指數(shù)1010寫成6q r的形式，還需取6為模來計(jì)算101°。為此我們有 _ _.22_ _ 3310 4(mod6),進(jìn)而有 104 4(mod 6) , 104 4(mod 6),依次類推，有1010 4(mod 6),所以 1010 6q 4(mod 6)從而，a 106q 4 (106)q 104 1q 104 34 4(mod 7)這樣，星期一后的第 a天將是星期五。例5.求所有的素?cái)?shù) p,使4p2

19、1與6p2 1也是素?cái)?shù)。分析：要使4p2 1與6p2 1也是素?cái)?shù)，應(yīng)該是對(duì)p除以某個(gè)數(shù)素q的余數(shù)進(jìn)行分類討論，最后確定p只能是這個(gè)素?cái)?shù)。由于只有兩個(gè)數(shù)，所以q不能太大，那樣討論起來也不會(huì)有什么效果，試驗(yàn) q 2,3發(fā)現(xiàn)對(duì)本題不起任何效果，現(xiàn)對(duì) q 5展開討論。解：設(shè) u 4p2 1, v 6p2 1,且 p 5k 1, k Z,r 0,1,2,3,4若 r 1或 4 時(shí)，p2 1(mod5), u 4p2 1 4 1 0(mod 5)；22右 r 2或 3 時(shí)，p4(mod 5) , v 6 p 1 24 1 0(mod 5)；即r 0時(shí)，u,v為5的倍數(shù)且比5大，不為質(zhì)數(shù)。故 r 0,此時(shí)p

20、 5,_2_ _ 2u 54 1 101 ； v 56 1 151 都是素?cái)?shù)。即可題有唯一解 p 5。注：要使幾個(gè)數(shù)同為質(zhì)數(shù)，一般是對(duì)這幾個(gè)數(shù)也合乎以某一質(zhì)數(shù)的余數(shù)來確定，如p, p 2, p 4均為質(zhì)數(shù)，可得 p只能為3,由于這是p的一次式，故三個(gè)數(shù)就模 3,而二 次式對(duì)三個(gè)數(shù)就模 5,四個(gè)數(shù)一般就模 7 了。例6.求滿足112m 5n | 7的全部正整數(shù) m,n。分析：如果5n 12m 7,兩邊mod4,得1 3(mod 4),這是不可能的；如果12m 5n 7 ,而m,n中有一個(gè)大于 1,則另一個(gè)也大于 1, mod3得(1)n 1(mod 3),故 n 為奇數(shù)，mod8,得 5n 1(

21、mod8),而 52 1(mod 8), n 為奇數(shù)，從而 5 1(mod 8),矛盾！所以m n 1為唯一解。注：在解不定方程時(shí)，往往要分情況討論，也常常利用同余來導(dǎo)出一些性質(zhì)求出矛盾！小 宓,7an45a2 36例 7.數(shù)列an滿足：a01,an 1,n N.21為完全平方數(shù)。證明：(1)對(duì)任意n N,an為正整數(shù)；(2)對(duì)任意n N,anan1(2005年全國高中數(shù)學(xué)聯(lián)賽試題)(1 )由題設(shè)得a15,且an嚴(yán)格單調(diào)遞增.將條件式變形得2an 1 7an J45a2 36,兩邊平方整理得 a2 1 7anani222an 9 0 -得(an 1 an 1)(an 1 an 1 7an)0,Q an 1an, an 1an 17 an 0an 17 anab 1.由式及a01al 5可知，對(duì)任意nN, an為正整數(shù).an7anian an 1(2)將兩邊配方，得(an 1an)2 9(anan 1 1), anan 1 1(亙?yōu)鮈)2.3由式 an1an9an(an1an)三(anan1)mod3a . a 一-1 an1an = ( 1)a1a0=0(mod3。為正整數(shù),式成立.3anan 11是完全平方數(shù).一 . 3n 1,.一，, ,例8.若 3n 1可以寫成有限小數(shù)，那么自然數(shù) n的值是多少?n(2n 1)解：由