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

1、信息安全與保密,主講人：何毅,數(shù)論基礎(chǔ)——§1 整數(shù)的表示方法,包括正整數(shù)（自然數(shù)）、零和負(fù)整數(shù)。,§1 整數(shù)的表示法,整數(shù),數(shù)論基礎(chǔ)——§1 整數(shù)的表示方法,設(shè)m是大于1的正整數(shù)，則每一個正整數(shù)n可唯一表示為：,其中cj是整數(shù)，滿足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,依次類推可得，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每一個正整數(shù)a可以唯一地通過正整數(shù)b而被表示成,數(shù)q叫做a被b除的不完全商數(shù)，數(shù)r叫做a被b除的余數(shù)。,證明,例題2,數(shù)論基礎(chǔ)——§1 整數(shù)的表示方法,數(shù)論基礎(chǔ)——§1 整數(shù)的表示方法,證明：實際上，取qb等于b的倍數(shù)中不超過a的這種形式的一個表示式。假定還有,兩式相減得到,即,,。因|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ù)分解,素數(shù)只能被1和數(shù)自身整除的數(shù)稱為素數(shù)。,合數(shù)不是1且非素數(shù)的正整數(shù)稱為合數(shù)。即一個合數(shù)至少能被非1的

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

7、個公倍數(shù)，則稱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’。類似地，由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ù)，必有一個正的最大公因數(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。那么,依次類推，直到出現(xiàn)余數(shù)為零為止。這樣，存在某一整數(shù)k，使得,對于這個序列有,且,rk就是gcd{a,b}。證畢。本定理的證明提供了一個求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。該定理表明，兩個整數(shù)的最大公因子可以表示成這兩個整數(shù)的因數(shù)和。,證明,特別，若gcd{a,b}=1,則稱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。其證明過程也是得到這個式子的具體方法。由例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ù)分解,推論若素數(shù)p除盡a1a2…an，則必存在k：，使得p|ak。,證明：若p與a1互素，則p|a2…an；若p也與a2互素，則

14、p|a3…an；…. 。若p與a1，a2，… ，an-1的每一個互素，則最后有p|an。,數(shù)論基礎(chǔ)——§2 因數(shù)分解,定理5每一個正合數(shù)，可表示為正素數(shù)的乘積，并且不考慮乘積的順序時，表示法是唯一的。,由這個定理，若c有素數(shù)因子p1,p2,..,pn，那么c=p1α1p2α2…pnαn。這個式稱為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ù)以上步驟，直到不能分解因子為止。這個過程可在有限步內(nèi)完成，故有c=p1p2…pn。若這個分解不是唯一的，設(shè)c=q1q2…qm。那么p1p2…pn= q1q2…qm。素數(shù)p1| q1q2…qm，故存在qi，p1| qi，因qi也是素數(shù)，因此p1= qi。不妨設(shè)p1= q1，由于p1≠0可知p2p3…pn = q2q3…qm。繼續(xù)取盡所有的pi為止

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

17、a≡a mod m；2)對稱性，即若a≡b mod m，則b≡a mod m；3)傳遞性，即若a≡b mod m，b≡c mod m，則a≡c mod m。這三條性質(zhì)看起來是明顯的，證明從略。,數(shù)論基礎(chǔ)——§3 同余類,定理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 同余類,定理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 同余類,數(shù)論基礎(chǔ)——§3 同余類

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

21、基礎(chǔ)——§3 同余類,數(shù)論基礎(chǔ)——§3 同余類,非負(fù)最小剩余：一個類的什意數(shù)，對于同一個類的所有數(shù)而言，都叫作模m的剩余。我們得到的剩余正好等于余數(shù)r，叫做非負(fù)最小盛余。在上例中，每一個數(shù)都是模5的剩余；而3則是模5的非負(fù)最小剩余。注意：0≤3<5。對于余r的m個不同值，我們有m個由模m決定的數(shù)類。就是說，當(dāng)模m確定以后，有m個不同的余數(shù)r對應(yīng)的數(shù)類。,例 對于模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個數(shù)類。,數(shù)論基礎(chǔ)——§3 同余類,數(shù)論基礎(chǔ)——§3 同余類,完全剩余組從模m決定的每個數(shù)類中取一個剩余，我們得到模m的一個完全剩余組。,由于模m所決定的數(shù)類只有m個，故一個完全剩余組的元素也只有m個。

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

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

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

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

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

28、,數(shù)論基礎(chǔ)——§4 線性同余式,證明：若x0是（5）的一個解，則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’滿足同余式（5）。,數(shù)論基礎(chǔ)——§4 線性同余式,以上兩條定理給出三個常數(shù)a,b和m可以確定線性同余式的解，這使我們聯(lián)想到一元二次方程的系數(shù)解。下

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

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

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

32、連分式的Pn-1。,數(shù)論基礎(chǔ)——§4 線性同余式,例解同余式111x=75 mod 321——————————（*）解：第一步：判斷是否有解(111,321)=3，且3|75，故同余式有解，且有3個解。第二步：轉(zhuǎn)化成等價同余式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 線性同余式,第四步：求出所有的解x≡99；99+107；99+2×107 mod 321。也就是x≡99；206；313 mod 321。,數(shù)論基礎(chǔ)——§5 連立的同余式和中國剩余定理,定理1下列兩個同余式x≡b1 mod m1,x ≡b2 mod m2———————（9）有一個共同解的充要條件是b1≡b2 mo

34、d d,d=(m1,m2)————————（10）,證明：設(shè)x1滿足（9）的兩個同余式x≡b1+k1m1=b2+k2m2從而k2m2=b1-b2 mod m1由§4的定理1知，上式中k2存在的充要條件是：(m1,m2)|(b1-b2)。,定理2對于聯(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 連立的同余式和中國剩余定理,數(shù)論基礎(chǔ)——§5 連立的同余式和中國剩余定理,定理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 連立的同余式和中國剩余定理,中國剩余定理（孫子定理）（《孫子孫經(jīng)》中首次對此類問題的解法已作敘述）：若(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 連立的同余式和中國剩余定理,證明：令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)的解，且對于模m1m2…mk是唯一的。由于(mi,mj)=1,i≠j,故當(dāng)i≠h時，mh|Mj，有Mj≡0 mod mh，即x0中各項除第h項外，其余都模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 連立的同余式和中國剩余定理,下面證明其唯一性。如若不然，可設(shè)是同余方程組（11）的對于模M的另一個解，,則有即因此也就是,這就證明了對于模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 連立的同余式和中國剩余定理,數(shù)論基礎(chǔ)——§5 連立的同余式和中國剩余定理,例題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 連立的同余式和中國剩余定理,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得等價同余式y(tǒng)4≡-3 mod 7,即y4=4因而x=3×42+6×4×30 =126+720 =846 ≡6 mod 210,數(shù)論基礎(chǔ)——§6 歐拉定理和費爾馬定理,（1）可乘函數(shù)說f(a)函數(shù)說是可乘的，如果它適合下面的條件:1、函數(shù)對于所有的正整數(shù)a都有定義，而且至少對于一個這樣的a他不等于零；

43、2、對于任何互素的正數(shù)a1和a2都有f(a1 a2)=f(a1)f(a2),例對于任意實數(shù)或者指數(shù)s，指數(shù)函 φ(a)=as是可乘函數(shù)。,數(shù)論基礎(chǔ)——§6 歐拉定理和費爾馬定理,（2）歐拉函數(shù)φ(a)歐拉(Euler)函數(shù)對于所有正整數(shù)a都有意義，而且表示數(shù)列0，1，…, a-1里與a互素的數(shù)的個數(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 歐拉定理和費爾馬定理,,定理1若a1和a2互素則歐拉函數(shù)φ(a)φ(a1 a2 )=φ(a1) φ(a2)。,該定理給計算歐拉函數(shù)φ(a)值提供了極大的便利。例3φ（405）=φ（8）φ（5）=54×4=216,數(shù)論基礎(chǔ)——§6 歐拉定理和費爾馬定理,定理2設(shè),特別地,

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

46、馬定理,又由定理1可得,數(shù)論基礎(chǔ)——§6 歐拉定理和費爾馬定理,定理3對于模m兩兩不同余的任意φ(m)個與?；ニ氐臄?shù)，組成一個與模m互素的剩余組。,證明：實際上，由于不同余而且與?；ニ氐木壒剩@些數(shù)屬于不同的包含與?；ニ氐臄?shù)的類，而因為它們的個數(shù)φ(m)正好是這樣子的類的個數(shù)，所以在每個類里正好有一個數(shù)。,數(shù)論基礎(chǔ)——§6 歐拉定理和費爾馬定理,定理4如果(a,m)=1而且x通過與模m互素的剩余組，則ax也通

47、過與模m互素的剩余組。,證明：實際上，ax的個數(shù)與x一樣，即有φ(m)個。因此，只要證明所有的ax對于模m兩兩不同余而且都與?；ニ亍ＴO(shè)不同余的x1和x2對應(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沒有共同的素因子，因而與ax沒有共同的素因子，故(ax,m)=1。,數(shù)論基礎(chǔ)

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

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

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

51、的逆元素。解因210 ≡1 mod 11故對于mod 11，2的逆元素為29，而29=512≡6 mod 11,故6是2模11的逆。可以驗證，2×6≡1 mod 11。,定理5若p為素數(shù)，d=(a,p),且d|b,則ax≡b mod p有解答為,其中,為a對于模p的逆。,例7x≡22 mod 317模31的逆為9(因7×9=63≡1 mod 31),故得x ≡9 ×22=193

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

53、實際上，它是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個數(shù)分成(p-3)/2對互為逆元素。故(p-2)! ≡1 mod p(p-1)! ≡p-1 mod p ≡-1 mod p,,數(shù)論基礎(chǔ)——§7 威爾森定理,充分性假定(p-1)!≡-1 mod p，但p不是素數(shù)，即p=ab,其中11的假

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

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

56、再沒有其它不同余的解了.如若x’’和x’都是問題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故只有兩個解。,數(shù)論基礎(chǔ)——§8 平方剩余,數(shù)論基礎(chǔ)——§8 平方剩余,定理1若p是奇素數(shù)，則

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

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

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