數(shù)論基礎(chǔ) (1)

1、信息安全與保密,主講人：何毅,數(shù)論基礎(chǔ)——§1 整數(shù)的表示方法,包括正整數(shù)（自然數(shù)）、零和負(fù)整數(shù)。,§1 整數(shù)的表示法,整數(shù),數(shù)論基礎(chǔ)——§1 整數(shù)的表示方法,設(shè)m是大于1的正整數(shù)，則每一個(gè)正整數(shù)n可唯一表示為：,其中cj是整數(shù)，滿(mǎn)足0≤ cj <m，且ck≠0，這里j=0,1,2,…k.。,定理1,———（1）,證明,,例題1,數(shù)論基礎(chǔ)——§1 整數(shù)的表示方法,證明用,表示不

2、大于x的最大整數(shù)。,設(shè),，令,，則,其中C0是用m除n0的余數(shù)。一般地令,則有,這里nk+1=0。于是有,數(shù)論基礎(chǔ)——§1 整數(shù)的表示方法,其中,下面證明表示法（1）是唯一的。若不是唯一的，則設(shè),則有,(1),數(shù)論基礎(chǔ)——§1 整數(shù)的表示方法,其中,下面證明表示法（1）是唯一的。若不是唯一的，則設(shè),則有,(1),數(shù)論基礎(chǔ)——§1 整數(shù)的表示方法,所以有m|(d0-c0),而0≤ d0 <m

3、, 0≤ c0 <m,所以有, d0 = c0,(１)式兩邊同除以m得：,（2）,同樣可得， d1 = c1,依次類(lèi)推可得，k=l,,j=0,1,…,k。即表示法是唯一的。,證畢。,數(shù)論基礎(chǔ)——§1 整數(shù)的表示方法,例題1n = 389，m = 5。,，余數(shù)C0=4。,，余數(shù)C1=2。,，余數(shù)C2=0。,，余數(shù)C3=3。,即389=3·53+2·5+4，或389=(3024)5 。同樣可將n

4、=389表示為2進(jìn)制數(shù)如下：389 = (110000101)2 。,定理2每一個(gè)正整數(shù)a可以唯一地通過(guò)正整數(shù)b而被表示成,數(shù)q叫做a被b除的不完全商數(shù)，數(shù)r叫做a被b除的余數(shù)。,證明,例題2,數(shù)論基礎(chǔ)——§1 整數(shù)的表示方法,數(shù)論基礎(chǔ)——§1 整數(shù)的表示方法,證明：實(shí)際上，取qb等于b的倍數(shù)中不超過(guò)a的這種形式的一個(gè)表示式。假定還有,兩式相減得到,即,,。因|r-r1|<b,，只有r=r1才可能，

5、是有,證畢,數(shù)論基礎(chǔ)——§1 整數(shù)的表示方法,例題2設(shè)b=14,我們有177=12×14+90 ≤ 9<14-64=(-5) ×14+60≤6<14154=11 ×14+00 ≤0<14,數(shù)論基礎(chǔ)——§2 因數(shù)分解,§2 因數(shù)分解,素?cái)?shù)只能被1和數(shù)自身整除的數(shù)稱(chēng)為素?cái)?shù)。,合數(shù)不是1且非素?cái)?shù)的正整數(shù)稱(chēng)為合數(shù)。即一個(gè)合數(shù)至少能被非1的

6、兩個(gè)整數(shù)整除。,最大公因子：用a,b,c為正整數(shù)，a除盡b表示為a|b。若a|b，且a|c，就是說(shuō)a是b何c的公因子。若a是b和c的公因子，且b和c的每一個(gè)公因子都能除盡a，則稱(chēng)a是b和c的最大公因子，用gcd{b,c}或（b,c）表示。即,，或,例12=gcd(12,60),數(shù)論基礎(chǔ)——§2 因數(shù)分解,最小公倍數(shù)若a|c，則稱(chēng)c是a的倍數(shù)。若a|c，b|c，則稱(chēng)c是a和b的公倍數(shù)；如果a和b的公倍數(shù)c除盡a和b的什何一

7、個(gè)公倍數(shù)，則稱(chēng)c是a和b的最小公倍數(shù)，表示為,，或,例60 = lcm{15,20,30},下面有關(guān)因數(shù)分解的5條定理。,數(shù)論基礎(chǔ)——§2 因數(shù)分解,定理1若a=bq+r，則,證明,證明：設(shè)d=(a,b),d’=(b,r)，則d|(a-bq)，即d|r。所以d是b和r的公因數(shù)，即d|d’。類(lèi)似地，由d’|(dq+r)可得d’|a，所以d’|d。由d|d’，可令d’=hd；由d’|d，可令d=kd’。即有d’=hk

8、d’，因，所以有hk=1。H=k=±1, d=±d’。證畢。,數(shù)論基礎(chǔ)——§2 因數(shù)分解,,定理2每一雙不為零的整數(shù)，必有一個(gè)正的最大公因數(shù)。,數(shù)論基礎(chǔ)——§2 因數(shù)分解,證明,例題1,數(shù)論基礎(chǔ)——§2 因數(shù)分解,證明：不失一般性，設(shè)a和b是正整數(shù)，且a>b。令a=bq+r，0≤r<b。由定理1可得(a,b)=(b,r)。又令b=rq1+r1，0≤r1&l

9、t;r。那么,依次類(lèi)推，直到出現(xiàn)余數(shù)為零為止。這樣，存在某一整數(shù)k，使得,對(duì)于這個(gè)序列有,且,rk就是gcd{a,b}。證畢。本定理的證明提供了一個(gè)求gcd{a,b}的具體步驟。,數(shù)論基礎(chǔ)——§2 因數(shù)分解,數(shù)論基礎(chǔ)——§2 因數(shù)分解,例1求gcd{726,393}。726=1×393+333393=1×333+60333=5×60+3360=1×

10、;33+2733=1×27+627=4×6+36=2×3+0故gcd{726,393}=3,數(shù)論基礎(chǔ)——§2 因數(shù)分解,定理3若d=gcd{a,b},則存在整數(shù)p和q，使得d=pa+qb。該定理表明，兩個(gè)整數(shù)的最大公因子可以表示成這兩個(gè)整數(shù)的因數(shù)和。,證明,特別，若gcd{a,b}=1,則稱(chēng)a和b互素。因此根據(jù)定理3，若a和b互素，則存在整數(shù)p和q，使得pa+qb=1,數(shù)

11、論基礎(chǔ)——§2 因數(shù)分解,證明：由定理2的證明可得,……,依次消去rk-1，rk-2，…，r，可得d=rk=pa+qb。其證明過(guò)程也是得到這個(gè)式子的具體方法。由例1反推得,數(shù)論基礎(chǔ)——§2 因數(shù)分解,3 = 27 - 4×6 = 27 - 4×(33 - 27) = -4×33+5×27 = -4×33+5×(60-33) = 5&

12、#215;60-9×33 = 5×60-9×(333-5×60) = -9×333+50×60 = -9×33+50×(393-333) = 50×393-59×333 = 50×393-59×333 = 50×393-59×(726-393) = -59×72

13、6+109×393,數(shù)論基礎(chǔ)——§2 因數(shù)分解,定理4若a|bc，gcd{a,b}=1，那么a|c。證明：若a和b互素，則存在p、q使得pa+qb=1，兩邊同乘以c得，pac+qbc=c由假定，a|bc，所以a能除盡等式的左端，因此a|c。,數(shù)論基礎(chǔ)——§2 因數(shù)分解,推論若素?cái)?shù)p除盡a1a2…an，則必存在k：，使得p|ak。,證明：若p與a1互素，則p|a2…an；若p也與a2互素，則

14、p|a3…an；…. 。若p與a1，a2，… ，an-1的每一個(gè)互素，則最后有p|an。,數(shù)論基礎(chǔ)——§2 因數(shù)分解,定理5每一個(gè)正合數(shù)，可表示為正素?cái)?shù)的乘積，并且不考慮乘積的順序時(shí)，表示法是唯一的。,由這個(gè)定理，若c有素?cái)?shù)因子p1,p2,..,pn，那么c=p1α1p2α2…pnαn。這個(gè)式稱(chēng)為c的標(biāo)準(zhǔn)分解式。,證明,數(shù)論基礎(chǔ)——§2 因數(shù)分解,證明：若c是合數(shù)，則存在a和b，使得c=ab；若a和b是

15、合數(shù)，可設(shè)a=a1a2，b=b1b2，從而c=a1a2b1b2；繼續(xù)以上步驟，直到不能分解因子為止。這個(gè)過(guò)程可在有限步內(nèi)完成，故有c=p1p2…pn。若這個(gè)分解不是唯一的，設(shè)c=q1q2…qm。那么p1p2…pn= q1q2…qm。素?cái)?shù)p1| q1q2…qm，故存在qi，p1| qi，因qi也是素?cái)?shù)，因此p1= qi。不妨設(shè)p1= q1，由于p1≠0可知p2p3…pn = q2q3…qm。繼續(xù)取盡所有的pi為止

16、。所以n=m，分解是唯一的。,數(shù)論基礎(chǔ)——§3 同余類(lèi),同余：若m|(a-b)，即a-b=km，我們就說(shuō)a和b模m同余，記為a≡b mod m有時(shí)記為a≡b (mod m)。,例將整數(shù)a和b用模m和余來(lái)表示a=qam+r，b=qbm+r這里，r<a，r<b，是關(guān)于模m的余。因此有a-b=(qa-qb)m=km。,數(shù)論基礎(chǔ)——§3 同余類(lèi),定理1模m的同余關(guān)系滿(mǎn)足1)自反性，即

17、a≡a mod m；2)對(duì)稱(chēng)性，即若a≡b mod m，則b≡a mod m；3)傳遞性，即若a≡b mod m，b≡c mod m，則a≡c mod m。這三條性質(zhì)看起來(lái)是明顯的，證明從略。,數(shù)論基礎(chǔ)——§3 同余類(lèi),定理2若a≡b mod m，c≡d mod m，則1)a±c≡b±d mod m；2)ac≡bd mod m；,證明：因a≡b mod m，c≡d mod m，所

18、以a = km+b,c=hm+da±c=(k±h)m+(b±d)從而a±c≡b±d mod m。同理可證：ac≡bd mod m。證畢。,定理3若ac≡bc mod m，且c和m互素，則a≡b mod m。,證明：因ac≡bc mod m，可知ac=km+bc即c(a-b)=km由于c和m互素，因此c|k。設(shè)k=hc，則c(a-b)=hcmc-b

19、=hm即a≡b mod m。,數(shù)論基礎(chǔ)——§3 同余類(lèi),定理4若ac≡bc mod m，d=(c,m)，則a≡b mod m/d。,證明：因d=(c,m)，故d|c，d|m.可令c=c1d，m=m1d，得(c1,m1)=1,ac1≡bc1 mod m1。由定理3可得a≡b mod m1，即a≡b mod m/d。證畢。,數(shù)論基礎(chǔ)——§3 同余類(lèi),數(shù)論基礎(chǔ)——§3 同余類(lèi)

20、,,例60=42 mod 9，而3=(6,9)，60=10×6，42=7×6，9/3=3故10≡7 mod 3。,同余類(lèi) 對(duì)于模m同余的數(shù)組成由模m決定的數(shù)類(lèi)。就是說(shuō)，一個(gè)模決定了一個(gè)數(shù)類(lèi)。因此，與同一個(gè)類(lèi)的所有數(shù)對(duì)應(yīng)的是同一個(gè)余數(shù)r，而且只要在式子mq+r里讓q通過(guò)所有的整數(shù)，我們就得到這個(gè)類(lèi)的所有數(shù)。例對(duì)于模5，數(shù)列…,-12,-7,-2,3,8,13,…屬于同一個(gè)數(shù)類(lèi)。,數(shù)論

21、基礎(chǔ)——§3 同余類(lèi),數(shù)論基礎(chǔ)——§3 同余類(lèi),非負(fù)最小剩余：一個(gè)類(lèi)的什意數(shù)，對(duì)于同一個(gè)類(lèi)的所有數(shù)而言，都叫作模m的剩余。我們得到的剩余正好等于余數(shù)r，叫做非負(fù)最小盛余。在上例中，每一個(gè)數(shù)都是模5的剩余；而3則是模5的非負(fù)最小剩余。注意：0≤3<5。對(duì)于余r的m個(gè)不同值，我們有m個(gè)由模m決定的數(shù)類(lèi)。就是說(shuō)，當(dāng)模m確定以后，有m個(gè)不同的余數(shù)r對(duì)應(yīng)的數(shù)類(lèi)。,例 對(duì)于模5，數(shù)列…,-11,-6,-1

22、,4,9,14,…;r=4…,-13,-8,-3,2,7,12,…;r=2…,-14,-9,-4,1,6,11,…;r=1…,-15,-10,-5,0,5,10,…;r=0分別為模5決定的4個(gè)數(shù)類(lèi)。,數(shù)論基礎(chǔ)——§3 同余類(lèi),數(shù)論基礎(chǔ)——§3 同余類(lèi),完全剩余組從模m決定的每個(gè)數(shù)類(lèi)中取一個(gè)剩余，我們得到模m的一個(gè)完全剩余組。,由于模m所決定的數(shù)類(lèi)只有m個(gè)，故一個(gè)完全剩余組的元素也只有m個(gè)。

23、對(duì)于模m的兩兩不同余的任意m個(gè)數(shù)，組成這個(gè)模的完全剩余組。顯然模m的一個(gè)完全剩余組可以有無(wú)窮多個(gè)。而最常取作完全剩余組的是非負(fù)最小剩余0,1,2…m-1。,數(shù)論基礎(chǔ)——§3 同余類(lèi),例從上面兩例的每一個(gè)數(shù)類(lèi)中各任取一個(gè)數(shù)組成數(shù)組 –12，-11，2，1，10，稱(chēng)為組成模5的一個(gè)完全剩余組，其中元素只有5個(gè)，它們對(duì)于模5是兩兩不同余的。而數(shù)組0，1，2，3，4為模5的一個(gè)非負(fù)的最小剩余組。,數(shù)論基礎(chǔ)——

24、67;3 同余類(lèi),與模互素的剩余組：模m的同一個(gè)類(lèi)里的數(shù)與模有同一個(gè)最大公約數(shù)。其中特別重要的是這個(gè)公約數(shù)等于1的類(lèi)，它包含著與?；ニ氐臄?shù)的類(lèi)。,從每個(gè)這樣的與模互素的數(shù)類(lèi)中取一個(gè)剩余，便得到與模m互素的剩余組。,因此，可以取完全剩余組里與模互素的數(shù)來(lái)組成與?；ニ氐氖Ｓ嘟M。通常與?；ニ氐氖Ｓ嘟M從非負(fù)的最小剩余組0，1，2，… ，m-1中分出。,例數(shù)組0，1，2，3，4為模5的一個(gè)非負(fù)的最小剩余組，而數(shù)組1，2，3，4為模5互素的剩余組

25、。,數(shù)論基礎(chǔ)——§4 線(xiàn)性同余式,基本概念：研究下列形狀含有味知數(shù)x的同余式f(x)=0 mod m;f(x)=axn+a1xn-1+…+an —————————(1)如果a不被m除盡，則n叫作同余式的次數(shù)。當(dāng)n=1時(shí)，式(1)寫(xiě)成ax+a1=0 mod m ————————————(2)稱(chēng)為線(xiàn)性同余式（又稱(chēng)一次同余式）。將上式左邊的自由項(xiàng)移到右邊就寫(xiě)成了書(shū)上的形式ax≡b mod m ———

26、——————————(3),數(shù)論基礎(chǔ)——§4 線(xiàn)性同余式,同余解解同余式也就是類(lèi)似于解方程一樣要找出適合上列同余式的所有x來(lái)。x的同一些值所適合的兩個(gè)同余式叫作等價(jià)的。若整數(shù)x1滿(mǎn)足ax≡b mod m ———————————(4)即ax1≡b mod m，則可以證明，對(duì)于模m與x1同余的所有數(shù)都滿(mǎn)足這個(gè)線(xiàn)性同余式。則模m和x1同余的整數(shù)構(gòu)成同余式（1）x≡x1 mod m的同余解。,例對(duì)于2x≡3

27、 mod 5，可求得x≡4 mod 5是它的解。如x=9,14,19,…,數(shù)論基礎(chǔ)——§4 線(xiàn)性同余式,定理1同余式ax ≡b mod m———————————（5）有解的從要條件是d|b,其中d=(a,m)。令m’=m/d。若x0是（5）式的一個(gè)解，則（5）的所有解x均滿(mǎn)足x≡x0 mod m’。,定理2設(shè)d=(a,m)>1，d|b，則同余式ax ≡ b mod m,關(guān)于同余解有下面的兩個(gè)定理。

28、,數(shù)論基礎(chǔ)——§4 線(xiàn)性同余式,證明：若x0是（5）的一個(gè)解，則ax0 - km=b所以，d=(a,m)除盡b，即d|b。反之，若d|b，令b=b’d，a=a’d，m=m’d，則有(a’,m’)=1，即存在整數(shù)p和q，使得pa’+qm’=1 即pb’滿(mǎn)足同余式（5）。,數(shù)論基礎(chǔ)——§4 線(xiàn)性同余式,以上兩條定理給出三個(gè)常數(shù)a,b和m可以確定線(xiàn)性同余式的解，這使我們聯(lián)想到一元二次方程的系數(shù)解。下

29、面給出求d個(gè)解的方法；令a=a1d,b=b1d,m=m1d。式（5）等價(jià)于約去d以后的同余式a1x=b1 mod m1——————————（6）其中已經(jīng)有(a1,m1)=1，它對(duì)于模m1有一個(gè)解。令其解為x1，即x≡x1 mod m1。則對(duì)于模m，同余式（5）的問(wèn)題便簡(jiǎn)化為同余式（6）。探求同余式（6）的解答，可用基于連分式理論的一種方法。,數(shù)論基礎(chǔ)——§4 線(xiàn)性同余式,連分式對(duì)任一有理數(shù)m/a，分割成

30、有限的連分?jǐn)?shù)形式,上連分式課表示為,數(shù)論基礎(chǔ)——§4 線(xiàn)性同余式,其中在連分式里出現(xiàn)的數(shù)q1，q2，… ，叫做不完全商數(shù)，分?jǐn)?shù),叫做m/a的近似分?jǐn)?shù)。對(duì)于近似分?jǐn)?shù)，可以很容易地找到一個(gè)非常簡(jiǎn)單的規(guī)律：假定P0=1,Q0=0，P1=q1,Q1=1并且依次把近似分?jǐn)?shù)寫(xiě)成,數(shù)論基礎(chǔ)——§4 線(xiàn)性同余式,則有遞推公式,可以證明，遞推公式中各因子還有關(guān)系,———————（7）,并且可以做出一個(gè)表示確定各級(jí)近似分?jǐn)?shù)的分子

31、和分母：,數(shù)論基礎(chǔ)——§4 線(xiàn)性同余式,例如對(duì)于分?jǐn)?shù)105/38，其各級(jí)近似的分子和分母：,由此表由此表可以驗(yàn)證式(7)：105×17-38 × 47=(-1)5=-1,同余式(6)的解討論最后兩個(gè)鄰近的近似分?jǐn)?shù)（用a1代替a）：,由連分式的性質(zhì)式（7）得,因此兩邊同乘b得,數(shù)論基礎(chǔ)——§4 線(xiàn)性同余式,與式(6)比較，同余解為,——————————（8）,這里，求同余式便轉(zhuǎn)化成了求

32、連分式的Pn-1。,數(shù)論基礎(chǔ)——§4 線(xiàn)性同余式,例解同余式111x=75 mod 321——————————（*）解：第一步：判斷是否有解(111,321)=3，且3|75，故同余式有解，且有3個(gè)解。第二步：轉(zhuǎn)化成等價(jià)同余式37=25 mod 107———————————（**）第三步：求n和Pn-1。,因此得，n=4,Pn-1=26，而=25，故同余式（**）解為x≡-26×25≡10

33、7 × 7-650≡99 mod 107,數(shù)論基礎(chǔ)——§4 線(xiàn)性同余式,第四步：求出所有的解x≡99；99+107；99+2×107 mod 321。也就是x≡99；206；313 mod 321。,數(shù)論基礎(chǔ)——§5 連立的同余式和中國(guó)剩余定理,定理1下列兩個(gè)同余式x≡b1 mod m1,x ≡b2 mod m2———————（9）有一個(gè)共同解的充要條件是b1≡b2 mo

34、d d,d=(m1,m2)————————（10）,證明：設(shè)x1滿(mǎn)足（9）的兩個(gè)同余式x≡b1+k1m1=b2+k2m2從而k2m2=b1-b2 mod m1由§4的定理1知，上式中k2存在的充要條件是：(m1,m2)|(b1-b2)。,定理2對(duì)于聯(lián)立同余式x≡bi mod mi，i=1,2,…,n有一共同的解的充要條件是：(mi, mj)|(bi - bj)，i≠j,i, j=1,2,…,n。證

35、明：略。,數(shù)論基礎(chǔ)——§5 連立的同余式和中國(guó)剩余定理,數(shù)論基礎(chǔ)——§5 連立的同余式和中國(guó)剩余定理,定理3若a≡b mod m1, a≡b mod m2,..., a≡b mod mk,則a≡b mod [m1,m2,…, mk]。,證明：因a≡b mod mI，i=1,2,…,k所以mi|(a-b),i=1,2,…,k.所以[m1,m2,…,mk]|(a-b)從而a≡b mod [m

36、1,m2,…, mk]。,數(shù)論基礎(chǔ)——§5 連立的同余式和中國(guó)剩余定理,中國(guó)剩余定理（孫子定理）（《孫子孫經(jīng)》中首次對(duì)此類(lèi)問(wèn)題的解法已作敘述）：若(mi,mj)=1,i≠j,則同余方程組x≡bi mod mi,i =1,2,…k———————（11）有唯一解x=x0 mod m1m2….mk————————（12）,證明,例題1,例題1,數(shù)論基礎(chǔ)——§5 連立的同余式和中國(guó)剩余定理,證明：令M=m1

37、m2…mkMj=M/mj=m1m2…mj-1mj+1…mk求yi使Mjyj≡1 mod mj,j=1,2,…,k由于(Mj,mj)=1,所以解yj是存在的?？闪顇0=b1M1y1+b2M2y2+…+bkMkyk?？勺C明x0便是同余方程組(11)的解，且對(duì)于模m1m2…mk是唯一的。由于(mi,mj)=1,i≠j,故當(dāng)i≠h時(shí)，mh|Mj，有Mj≡0 mod mh，即x0中各項(xiàng)除第h項(xiàng)外，其余都模mh同余于0，而M

38、hyh≡1 mod mh，故x0≡bhMhyh mod mh≡bh mod mh因此x=x0是同余方程組（11）的解。,根據(jù)因數(shù)分解的定理3有1=Mjyi+qmj,數(shù)論基礎(chǔ)——§5 連立的同余式和中國(guó)剩余定理,下面證明其唯一性。如若不然，可設(shè)是同余方程組（11）的對(duì)于模M的另一個(gè)解，,則有即因此也就是,這就證明了對(duì)于模M的解是唯一的。以上證明方法給出了求解的一種步驟。,例1求解x≡1 mod 2，x≡2

39、 mod 3, x≡3 mod 5。解：M=2×3×5=30M1=15,M2=10,M3=615y1=1 mod 2,y1=110y2=1 mod 3,y2=16y3=1mod 5,y3=1x=15+20+18=53=23 mod 30,數(shù)論基礎(chǔ)——§5 連立的同余式和中國(guó)剩余定理,數(shù)論基礎(chǔ)——§5 連立的同余式和中國(guó)剩余定理,例題2求解x≡0 mod 2, x≡

40、0 mod 3, x≡1 mod 5, x≡6 mod 7解：M=2×3×5×7=210M1=105,M2=70,M3=42,M4=30105y1=1 mod 2,y1=170y2=1 mod 3,y2=142y3=1 mod 5, y3可如下方法解出42=8×5+2，5=2×2+1因此有1=5-2×2 =5-2×（42-85）

41、 =17×5-2×42故有同余式42×（-2）≡1 mod 5得y3≡-2 mod 5, 即y3=3.,數(shù)論基礎(chǔ)——§5 連立的同余式和中國(guó)剩余定理,30 y4≡1 mod 7, y4可如下方法解出30=7×4+2,7=3×2+1因此有1=7-3×2 =7-3×(30-7×4) =13×7-3×

42、;30故有同余式30×（-3）≡1 mod 7得等價(jià)同余式y(tǒng)4≡-3 mod 7,即y4=4因而x=3×42+6×4×30 =126+720 =846 ≡6 mod 210,數(shù)論基礎(chǔ)——§6 歐拉定理和費(fèi)爾馬定理,（1）可乘函數(shù)說(shuō)f(a)函數(shù)說(shuō)是可乘的，如果它適合下面的條件:1、函數(shù)對(duì)于所有的正整數(shù)a都有定義，而且至少對(duì)于一個(gè)這樣的a他不等于零；

43、2、對(duì)于任何互素的正數(shù)a1和a2都有f(a1 a2)=f(a1)f(a2),例對(duì)于任意實(shí)數(shù)或者指數(shù)s，指數(shù)函 φ(a)=as是可乘函數(shù)。,數(shù)論基礎(chǔ)——§6 歐拉定理和費(fèi)爾馬定理,（2）歐拉函數(shù)φ(a)歐拉(Euler)函數(shù)對(duì)于所有正整數(shù)a都有意義，而且表示數(shù)列0，1，…, a-1里與a互素的數(shù)的個(gè)數(shù)。例φ(1)=1, φ(2)=1, φ(3)=2, φ(4)=2, φ(5)=4, φ(6)

44、=2, φ(7)=6, φ(8)=4, φ(9)=6, φ(10)=4, φ(11)=10,數(shù)論基礎(chǔ)——§6 歐拉定理和費(fèi)爾馬定理,,定理1若a1和a2互素則歐拉函數(shù)φ(a)φ(a1 a2 )=φ(a1) φ(a2)。,該定理給計(jì)算歐拉函數(shù)φ(a)值提供了極大的便利。例3φ（405）=φ（8）φ（5）=54×4=216,數(shù)論基礎(chǔ)——§6 歐拉定理和費(fèi)爾馬定理,定理2設(shè),特別地,

45、是a的標(biāo)準(zhǔn)分解式。則,數(shù)論基礎(chǔ)——§6 歐拉定理和費(fèi)爾馬定理,證明：首先，證明對(duì)于素?cái)?shù)p有,因p為素?cái)?shù)，故在區(qū)間上的所有整數(shù)，要么是p的倍數(shù)，要么與pa互素。其中p的倍數(shù)為0,p,2p,…,(pa-1-1)p共為pa-1個(gè)。所以和pa互素的數(shù)的數(shù)目為 pa-pa-1= pa(1-1/p)故有φ(pa)= pa(1-1/p).當(dāng)a=1時(shí)，φ(pa)= p-1,數(shù)論基礎(chǔ)——§6 歐拉定理和費(fèi)爾

46、馬定理,又由定理1可得,數(shù)論基礎(chǔ)——§6 歐拉定理和費(fèi)爾馬定理,定理3對(duì)于模m兩兩不同余的任意φ(m)個(gè)與模互素的數(shù)，組成一個(gè)與模m互素的剩余組。,證明：實(shí)際上，由于不同余而且與模互素的緣故，這些數(shù)屬于不同的包含與模互素的數(shù)的類(lèi)，而因?yàn)樗鼈兊膫€(gè)數(shù)φ(m)正好是這樣子的類(lèi)的個(gè)數(shù)，所以在每個(gè)類(lèi)里正好有一個(gè)數(shù)。,數(shù)論基礎(chǔ)——§6 歐拉定理和費(fèi)爾馬定理,定理4如果(a,m)=1而且x通過(guò)與模m互素的剩余組，則ax也通

47、過(guò)與模m互素的剩余組。,證明：實(shí)際上，ax的個(gè)數(shù)與x一樣，即有φ(m)個(gè)。因此，只要證明所有的ax對(duì)于模m兩兩不同余而且都與?；ニ?。設(shè)不同余的x1和x2對(duì)應(yīng)的ax1和ax2也不同余，否則有ax1≡ax2 mod m,而(a,m)=1，我們將得到x1≡x2 mod m,這與數(shù)x1和x2不同余矛盾。另一方面，由于(a,m)=1，(x,m)=1，m和a或與x沒(méi)有共同的素因子，因而與ax沒(méi)有共同的素因子，故(ax,m)=1。,數(shù)論基礎(chǔ)

48、——§6 歐拉定理和費(fèi)爾馬定理,（3）歐拉定理當(dāng)m>1和(a,m)=1時(shí)，我們有aφ(m)≡1 mod m。,數(shù)論基礎(chǔ)——§6 歐拉定理和費(fèi)爾馬定理,證明：如果x通過(guò)從非負(fù)的最小剩余得來(lái)的與?；ニ氐氖Ｓ嘟M：x=r1,r2,…,rc,c=φ(m)則由定理4知，ax的非負(fù)的最小剩余ρ1, ρ2, …,ρc,也通過(guò)這樣的組，只是一般說(shuō)來(lái)次序有變動(dòng)罷了。把同余式ari=ρi mod m,i=1,2

49、,..,c逐項(xiàng)相乘，得acr1r2…rc=ρ1ρ2…ρc mod m于是從兩邊約掉乘積r1r2…rc=ρ1ρ2…ρc，就得出 aφ(m)≡1 mod m,（4）費(fèi)爾馬定理當(dāng)p是素?cái)?shù)而且a不被除盡時(shí)，有ap-1≡1 mod p這是歐拉定理在m=p時(shí)的推論。這個(gè)定理還可以給予更便利的形式。在上面的同余式中兩邊乘上a，我們得到同余式ap≡a mod p它對(duì)于所有的整數(shù)a都正確，因?yàn)楫?dāng)a是p的倍數(shù)時(shí)它成立。,a對(duì)于模m的

50、逆元素記為 。從歐拉定理知aφ(m)≡1 mod m ，因?yàn)閍φ(m)≡aφ(m)-1a mod m, 故對(duì)于mod m，a的逆元素為=aφ(m)-1。,數(shù)論基礎(chǔ)——§6 歐拉定理和費(fèi)爾馬定理,數(shù)論基礎(chǔ)——§6 歐拉定理和費(fèi)爾馬定理,例求解3102≡? mod 11解從費(fèi)爾馬定理可知310≡1 mod 11故 3102=(310)1032≡9 mod 11,例對(duì)于mod 11，求2

51、的逆元素。解因210 ≡1 mod 11故對(duì)于mod 11，2的逆元素為29，而29=512≡6 mod 11,故6是2模11的逆?？梢则?yàn)證，2×6≡1 mod 11。,定理5若p為素?cái)?shù)，d=(a,p),且d|b,則ax≡b mod p有解答為,其中,為a對(duì)于模p的逆。,例7x≡22 mod 317模31的逆為9(因7×9=63≡1 mod 31),故得x ≡9 ×22=193

52、≡12 mod 31,數(shù)論基礎(chǔ)——§6 歐拉定理和費(fèi)爾馬定理,數(shù)論基礎(chǔ)——§7 威爾森定理,威爾森定理(Wilson)同余式(p-1)!≡-1 mod p成立的充要條件是：p為素?cái)?shù)。,數(shù)論基礎(chǔ)——§7 威爾森定理,證明：必要性p=2時(shí)，(p-1)!≡1≡-1 mod p.定理為真。P>2時(shí)，根據(jù)定理5,對(duì)整數(shù)a：1≤a<p,總存在a的逆元 ,滿(mǎn)足　a≡1 mod p。

53、實(shí)際上，它是ax ≡1 mod p的解。很容易證明x2≡1 mod p當(dāng)且僅當(dāng)x ≡1 或-1 mod p。所以1和p-1的逆元素是自身，其它元素2，3，…p-2中的p-3個(gè)數(shù)分成(p-3)/2對(duì)互為逆元素。故(p-2)! ≡1 mod p(p-1)! ≡p-1 mod p ≡-1 mod p,,數(shù)論基礎(chǔ)——§7 威爾森定理,充分性假定(p-1)!≡-1 mod p，但p不是素?cái)?shù)，即p=ab,其中11的假

54、定矛盾,故p是素?cái)?shù).,數(shù)論基礎(chǔ)——§8 平方剩余,,只要考慮下列同余式x2 ≡1, x2 ≡2, x2 ≡3, x2 ≡4 mod 5不難發(fā)現(xiàn)x=1,x=4 滿(mǎn)足 x2 ≡1 mod 5x=2,x=3 滿(mǎn)足 x2 ≡4 mod 5不存在整數(shù)滿(mǎn)足x2≡2 mod 5 或 x2 ≡3 mod 5 求解x2≡a mod p,其中a與p互素,且p是奇數(shù).若問(wèn)題有解,則稱(chēng)a是模p的平方剩余,否

55、則稱(chēng)為非平方剩余.,,數(shù)論基礎(chǔ)——§8 平方剩余,,引理 若p是奇素?cái)?shù),且p不能整除a,則x2 ≡a mod p或無(wú)解或有兩個(gè)模p不同余的解.,,證明 若x2 ≡a mod p有解x’,則不難驗(yàn)證-x’是另一個(gè)與x’不同余的解.因(- x’)2 ≡ x’2 ≡a mod p同時(shí)x’≠- x’ mod p否則2 ≡0 mod p這跟p是奇素?cái)?shù),且p不能整除a的假定相矛盾.

56、再?zèng)]有其它不同余的解了.如若x’’和x’都是問(wèn)題x2 ≡a mod p的解,則x’2 ≡x’’ 2 ≡a mod p從而x’2-x’’2=(x’- x’’)(x’+x’’) ≡0 mod p故p|(x’-x’’)或p|(x’+x’’)即 x’≡x’’ mod p 或x’≡-x’’ mod p故只有兩個(gè)解。,數(shù)論基礎(chǔ)——§8 平方剩余,數(shù)論基礎(chǔ)——§8 平方剩余,定理1若p是奇素?cái)?shù)，則

57、整數(shù)1，2，…，p-1中正好有(p-1)/2個(gè)模p的平方剩余，其余的(p-1)/2個(gè)是非平方剩余。,定理2如果a是模p的平方剩余，則a(p-1)/2≡1 mod p而如果a是模p的非平方剩余，則a(p-1)/2≡-1 mod p,數(shù)論基礎(chǔ)——§9 勒讓德符號(hào)(Legendre),定義令p是素?cái)?shù)，a是一整數(shù)，且p不能整除a,引進(jìn)符號(hào),（稱(chēng)為L(zhǎng)egendre符號(hào)）：,例取p=712≡62≡ 1,22≡52≡

58、4,32≡42≡2 mod 7所以,數(shù)論基礎(chǔ)——§9 勒讓德符號(hào)(Legendre),勒讓德符具有如下性質(zhì)：1、歐拉判別條件若p是奇素?cái)?shù)，且p不能整除a，則,2、若a≡b mod p,且p不能整除a,則,3、若p是奇素?cái)?shù)，且p不能整除ab，則,4、若p是奇素?cái)?shù)，則,5、若p是奇素?cái)?shù)，則,6、高斯定理逆定理設(shè)p、q為兩個(gè)不同的奇素?cái)?shù)，則,數(shù)論基礎(chǔ)——§9 勒讓德符號(hào)(Legendre),例考

59、慮同余式x2≡365 mod 1847是否有解。這里1847是素?cái)?shù)。解：,故方程有解。,數(shù)論基礎(chǔ)——§9 勒讓德符號(hào)(Legendre),例證明不定方程x2+23y=17無(wú)整數(shù)解。解：,這表明x2≡17 mod 23無(wú)解，因此方程無(wú)解。,數(shù)論基礎(chǔ)——§10 雅科比符號(hào)(Jacobi),雅科比符號(hào)是勒讓德符號(hào)的一種推廣。定義設(shè)n是奇的正整數(shù)，且,是n的標(biāo)準(zhǔn)分解式，則定義雅科比符號(hào)為,雅科比符號(hào)具有