資源描述：
《《剩余系和歐拉函數(shù)》課件1》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、2.4剩余系和歐拉函數(shù)人教B版數(shù)學(xué)選修4-6《初等數(shù)論初步》定義1對于正整數(shù)m，則m個整數(shù)0,1,…,m-1中與m互素的整數(shù)個數(shù)記做?(m),也就是Euler函數(shù)例如，容易驗證?(2)=1，?(4)=2，?(7)=6定義2設(shè)R是模m的一個剩余類，若有a?R，使得(a,m)=1，則稱R是模m的一個簡化剩余類。定義3對于正整數(shù)m，從模m的每個簡化剩余類中各取一個數(shù)xi，構(gòu)成一個集合{x1,x2,?,x?(m)}，稱為模m的一個簡化剩余系模m的一個簡化剩余系的元素個數(shù)是?(m)例1設(shè)m是一個正整數(shù),則①0,1,…,m-1中與
2、m互素的整數(shù)全體組成模m的一個簡化剩余系叫做模m的最小非負(fù)簡化剩余系②1,…,m-1,m中與m互素的整數(shù)全體組成模m的一個簡化剩余系叫做模m的最小正簡化剩余系③-m+1,…,-1,0中與m互素的整數(shù)全體組成模m的一個簡化剩余系叫做模m的最大非正簡化剩余系④-m,-m+1,…,1中與m互素的整數(shù)全體組成模m的一個簡化剩余系叫做模m的最大負(fù)簡化剩余系⑤當(dāng)m分別為偶數(shù)時,-m/2,-(m-2)/2,…,-1,0,1,…,(m-2)/2或-(m-2)/2,…,-1,0,1,…,(m-2)/2,m/2中與m互素的整數(shù)全體組成模m
3、的一個簡化剩余系當(dāng)m是奇數(shù)時,-(m-1)/2,…,-1,0,1,…,(m-1)/2中與是m互素的整數(shù)全體組成模m的一個簡化剩余系上述兩個簡化剩余系統(tǒng)稱為模m的一個絕對值最小簡化剩余系定理1若a1,a2,…,a?(m)是?(m)個與m互素的整數(shù),并且兩兩對模m不同余,則a1,a2,…,a?(m)是模m的一簡化剩余系定理2若(a,m)=1,rl,r2,…,r?(m)是模m的一簡化剩余系,則arl,ar2,…,ar?(m)也是模m的一簡化剩余系證明由定理1只需證明arl,ar2,…,ar?(m)是模m兩兩互不同余,且都與m
4、互素即可.先證兩兩互不相同:假設(shè)ari?arj(modm),其中1≤i,j≤?(m).由于(a,m)=1,有ri?rj(modm),這與rl,r2,…,r?(m)是模m的一簡化剩余系矛盾,故ari≠arj(modm),即:arl,ar2,…,ar?(m)中模m兩兩互不同余再證(a,m)=1,(r,m)=1,(ar,m)=1例2已知1,7,11,13,17,19,23,29是模30的簡化剩余系(7,30)=1,構(gòu)造一個簡化剩余系定理3設(shè)m是一個正整數(shù),(a,m)=1,則存在a’,使得aa’≡1(modm)證明,因為,(a
5、,m)=1故存在唯一的整數(shù)s,t滿足sa+tm=1?sa≡1(modm),取s=a’成立這里a’也叫做a模m的乘法逆元定理4設(shè)m1,m2?N，(m1,m2)=1，又設(shè)分別是模m1與m2的簡化剩余系，則A={m1y?m2x；x?X，y?Y}是模m1m2的簡化剩余系。定理5設(shè)m,n?N，(m,n)=1，則?(mn)=?(m)?(n)證,由定理4直接得到定理6設(shè)n的標(biāo)準(zhǔn)分解式是n=是它的全部素因數(shù)，則?(n)=證明:由定理5有?(n)=對任意的素數(shù)p，?(p?)等于數(shù)列1,2,?,p?中與p?（也就是與p）互素的整數(shù)的個數(shù)，
6、因此?(p?)=p??(1)又n=,和(1)式結(jié)合起來就得到結(jié)論推論設(shè)pq是不同的素數(shù),則?(pq)=?(p)?(q)=(p-1)(q-1)下面進(jìn)一步考察歐拉函數(shù)的性質(zhì)定理7設(shè)n是一個正整數(shù)則證明:設(shè)C={1,…,n},按照與n的最大公因素分類,對d
7、n記Cd={m
8、1≤m≤n,(m,n)=d},因為,(m,n)=diff,(m/d,n/d)=1,所以Cd中的元素m的形式Cd={m=dk
9、1≤k≤n/d,(k,n/d)=1},故Cd的元素個數(shù)為?(n/d),因為每個整數(shù)屬于且僅屬于一個類Cd因此,#C=,即,又當(dāng)d遍歷
10、n的正因素時,n/d也遍歷n的所有正因素例3設(shè)整數(shù)n=50,利用定理8對其進(jìn)行分類解,因為n的因素為1,2,5,10,15,25,50則C1={1,3,7,9,11,13,17,19,23,27,29,31,33,37,39,41,43,47,49}C2={2,4,6,8,12,14,16,18,22,24,26,28,32,34,36,3842,44,46,48}……..TheEnd
