1、第8章數(shù)論入門2,如果a|c，b|c，則稱c是a、b的公倍數(shù)。如果c是a、b的公倍數(shù)中最小者，則稱c是a、b的最小公倍數(shù)，記為：c=lcma,b例如：lcm15,20,30=60,最小公倍數(shù),只能被1和其本身整除的自然數(shù)稱為素?cái)?shù)，非素?cái)?shù)的正整數(shù)稱為合數(shù)。如2，3，5，7，11,素?cái)?shù),每一個(gè)比1大的整數(shù)，要么本身是一個(gè)素?cái)?shù)，要么可以寫成一系列不同素?cái)?shù)的乘積：所有ai均為正整數(shù)，不考慮乘積順序時(shí)，表示法是惟一的,例如，999999=3337111337,設(shè)a2是正整數(shù)，則：（1）如果a是合數(shù)，那么必存在素因子p(2)如果有素?cái)?shù)分解式a=p1ps，則存在素因子p素?cái)?shù)有無窮多個(gè)。,素?cái)?shù),Fermat定

2、理若p是素?cái)?shù)，a為任意正整數(shù)，則()若a與p互素，則該定理為11()例：計(jì)算243210(mod101)因?yàn)?1001(mod101)(2100)4322101432210102414(mod101),8.2Fermat定理和Euler定理,Euler函數(shù)：小于m且與m互素的正整數(shù)的個(gè)數(shù)稱為m的Euler函數(shù)，記為(m),習(xí)慣上(1)=1例：確定(37)和(35)的值。因?yàn)?7是素?cái)?shù)，所以從1到36的所有正整數(shù)均與37互素。故(37)=36列出所有小于35且與35互素的正整數(shù)如下：1，2，3，4，6，8，9，11，12，13，16，17，18，19，22，23，24，26，27，29，31，3

3、2，33，34共有24個(gè)數(shù)，所以(35)=24,8.2Euler定理和Fermat定理,Euler函數(shù)具有下面的重要性質(zhì)：(1)若p素?cái)?shù)，則：(p)=p-1例如：p=13,小于13的數(shù)1，2，3，4，5，6，7，8，9，10，11，12都與13互素。(13)=12.(2)若m,n互素，即gcd(m,n)=1，有(mn)=(m)(n)例如:(5*6)=(5)(6)=(5)(2)(3)=4*1*2=8進(jìn)一步，若n1,n2,，nm兩兩互素，則(n1n2nm)=(n1)(n2)(nm),8.2Euler定理和Fermat定理,（3）設(shè)m=p11p22pkk是m的標(biāo)準(zhǔn)分解式，p1，p2，pk是互不相同的

4、素?cái)?shù)，則(m)=m(1-1/p1)(1-1/p2)（1-1/pk）例如：20=22*51，這樣，(20)=20(1-1/2)(1-1/5)=8課堂練習(xí)：計(jì)算(9),8.2Euler定理和Fermat定理,2.Euler定理：若a和m互素,則a(m)1(modm).當(dāng)m為素?cái)?shù)時(shí)，即為Fermat定理形式例如：(1)a=3,m=10;(m)=(10)=(2)(5)=4;34=811(mod10).(2)a=2;m=11;(m)=(11)=10;210=10241(mod11)另一種形式：a(m)+1a(modm).,8.3Euler定理和Fermat定理,X2(mod3)X3(mod5)X2(mo

5、d7),解：?jiǎn)栴}歸結(jié)為解,南北朝時(shí)期孫子算經(jīng)中有“物不知數(shù)”問題：今有物不知其數(shù)，三三數(shù)之剩二，五五數(shù)之剩三，七七數(shù)之剩二，問物幾何？,8.4中國(guó)剩余定理,三人同行七十稀五樹梅花廿一枝七子團(tuán)圓月正半除百零五便得知,270321215=233，2331052=23,1,2,，是兩兩互素的正整數(shù)，設(shè)=12Mi=M/mi，MiMi-11(modmi)，則同余方程組：,Xb1(modm1)Xb2(modm2)Xbk(modmk),有模M的解x，,xM1M1-1b1+M2M2-1b2+MkMk-1bk(modM),8.4中國(guó)剩余定理,M=m1m2m3=3*5*7=105M1=M/m1=105/3=35M

6、2=M/m2=105/5=21M3=M/m3=105/7=15M1M1-11(modm1)M2M2-11(modm2)M3M3-11(modm3),35M1-11(mod3)得：M1-1221M2-11(mod5)M2-1115M3-11(mod7)M3-11,即：,8.4中國(guó)剩余定理,xM1M1-1b1+M2M2-1b2+M3M3-1b3(mod105)70b1+21b2+15b3(mod105)70*2+21*3+15*2(mod105)140+63+30(mod105)35+63+30(mod105)128(mod105)23(mod105)所以，此物有23個(gè),8.4中國(guó)剩余定理,課堂練

7、習(xí)：三位運(yùn)動(dòng)員跨臺(tái)階，臺(tái)階總數(shù)在100-150級(jí)之間，第一位運(yùn)動(dòng)員每次跨3級(jí)臺(tái)階，最后一步還剩2級(jí)臺(tái)階。第二位運(yùn)動(dòng)員每次跨4級(jí)臺(tái)階，最后一步還剩3級(jí)臺(tái)階。第三位運(yùn)動(dòng)員每次跨5級(jí)臺(tái)階，最后一步還剩4級(jí)臺(tái)階。問：這些臺(tái)階總共有多少級(jí)?A.119B.121C.129D.131,8.5離散對(duì)數(shù),由歐拉定理，對(duì)gcd(a,m)=1,有a(m)1(modm)，下面考慮更一般的形式，定義指數(shù)：設(shè)gcd(a,m)=1,使an1(modm)成立的最小正整數(shù)n稱為a對(duì)模m的指數(shù)或階、或a所產(chǎn)生的周期長(zhǎng)，記為m(a)。定義本原根：如果m(a)=(m)，則稱a是模m的本原根。,從上表中可以看出：（1）階為2元素有(2

8、)=1個(gè)；12模13的階為2。（2）階為3元素有(3)=2個(gè)；3，9模13的階為3。（3）階為4元素有(4)=2個(gè)；5，8模13的階為4。（4）階為6元素有(6)=2個(gè)；4，10模13的階為6。（5）階為12元素有(12)=(3)(22)=4個(gè)；2，6，7，11模13的階為12，等于(13)，所以2，6，7，11是模13的原根.,若a和p互素，且a為p的本原根，則其冪：a1，a2，a(p)模p兩兩不同余，且均與p互素。特別的，如果p為素?cái)?shù)，則對(duì)其本原根a，a的1到(p-1)的各次冪恰好可產(chǎn)生1到(p-1)每個(gè)整數(shù)一次且僅一次。即amodp，a2modp，ap-1modp=1，2，p-1=Zp*,對(duì)某素?cái)?shù)p的本原根a，a的1到(p-1)的各次冪恰好能產(chǎn)生1到(p-1)的每個(gè)整數(shù)一次且一次，而我們知道任何整數(shù)b滿足：()，其中0r(p-1)，只考慮非零元素，因此對(duì)任意非零整數(shù)b、素?cái)?shù)p的本原根a,有唯一的冪i，使得：(),其中1i(p-1)該指數(shù)i稱為以a為底(模p)b的離散對(duì)數(shù)，記為,(),離散對(duì)數(shù),離散對(duì)數(shù),模19的離散對(duì)數(shù)表,離散對(duì)數(shù)的計(jì)算：考慮一般形式的方程表示方式：y=gx(modp)對(duì)于給定的g、x、p，可直接計(jì)算出y。在最壞情況下需執(zhí)行x次乘法。但是，對(duì)于給定的g、y、p，當(dāng)p值很大時(shí)，計(jì)算x=dlogg,p(y)一般非常困難（即求離散對(duì)數(shù)）