《剩余系和歐拉函數(shù)》課件1優(yōu)質(zhì)公開(kāi)課人教B版選修46

1、2.4 剩余系和歐拉函數(shù)人教B版數(shù)學(xué)選修4-6初等數(shù)論初步2.4 剩余系和歐拉函數(shù)人教B版數(shù)學(xué)選修4-6初等數(shù)論初定義1 對(duì)于正整數(shù)m，則m個(gè)整數(shù)0,1,m-1中與m互素的整數(shù)個(gè)數(shù)記做(m) ,也就是Euler函數(shù) 例如，容易驗(yàn)證(2) = 1，(4) = 2，(7) = 6 定義2設(shè)R是模m的一個(gè)剩余類(lèi)，若有aR，使得(a, m) = 1，則稱(chēng)R是模m的一個(gè)簡(jiǎn)化剩余類(lèi)。定義3 對(duì)于正整數(shù)m，從模m的每個(gè)簡(jiǎn)化剩余類(lèi)中各取一個(gè)數(shù)xi，構(gòu)成一個(gè)集合x(chóng)1, x2, ,x(m) ，稱(chēng)為模m的一個(gè)簡(jiǎn)化剩余系模m的一個(gè)簡(jiǎn)化剩余系的元素個(gè)數(shù)是(m) 定義1 對(duì)于正整數(shù)m，則m個(gè)整數(shù)0,1,m-1中與m互素

2、例1設(shè)m是一個(gè)正整數(shù),則0,1,m-1中與m互素的整數(shù)全體組成模m的一個(gè)簡(jiǎn)化剩余系叫做模m的最小非負(fù)簡(jiǎn)化剩余系 1,m-1,m中與m互素的整數(shù)全體組成模m的一個(gè)簡(jiǎn)化剩余系叫做模m的最小正簡(jiǎn)化剩余系-m+1,-1,0中與m互素的整數(shù)全體組成模m的一個(gè)簡(jiǎn)化剩余系叫做模m的最大非正簡(jiǎn)化剩余系-m,-m+1,1中與m互素的整數(shù)全體組成模m的一個(gè)簡(jiǎn)化剩余系叫做模m的最大負(fù)簡(jiǎn)化剩余系 例1設(shè)m是一個(gè)正整數(shù),則當(dāng)m分別為偶數(shù)時(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的一個(gè)簡(jiǎn)化剩余系當(dāng)m是奇數(shù)時(shí),-(m-1

3、)/2,-1,0,1,(m-1)/2中與是m互素的整數(shù)全體組成模m的一個(gè)簡(jiǎn)化剩余系上述兩個(gè)簡(jiǎn)化剩余系統(tǒng)稱(chēng)為模m的一個(gè)絕對(duì)值最小簡(jiǎn)化剩余系當(dāng)m分別為偶數(shù)時(shí),定理1若a1,a2,a(m)是(m)個(gè)與m互素的整數(shù), 并且兩兩對(duì)模m不同余,則a1,a2,a(m)是模m的一簡(jiǎn)化剩余系定理2若(a,m)=1, rl,r2,r(m)是模 m的一簡(jiǎn)化剩余系, 則arl,ar2,ar (m)也是模m的一簡(jiǎn)化剩余系定理1若a1,a2,a(m)是(m)個(gè)與m互素的整數(shù)證明 由定理1只需證明arl,ar2,ar (m)是模m兩兩互不同余, 且都與m互素即可. 先證兩兩互不相同:假設(shè)ariarj(mod m), 其中1

4、i, j (m). 由于(a,m)=1, 有rirj(mod m), 這與rl,r2,r(m)是模 m的一簡(jiǎn)化剩余系矛盾, 故ariarj(mod m), 即: arl,ar2,ar (m)中模m兩兩互不同余證明 由定理1只需證明arl,ar2,ar (m)是再證(a,m)=1,(r,m)=1,(ar,m)=1例2 已知1,7,11,13,17,19,23,29是模30的簡(jiǎn)化剩余系 (7,30)=1 ,構(gòu)造一個(gè)簡(jiǎn)化剩余系再證(a,m)=1,(r,m)=1,(ar,m)=1定理 3 設(shè)m是一個(gè)正整數(shù),(a,m)=1, 則存在a ,使得a a 1(mod m)證明,因?yàn)?(a,m)=1 故存在唯一

5、的整數(shù)s,t 滿(mǎn)足sa+tm=1 sa 1(mod m), 取s= a 成立這里 a 也叫做a模m的乘法逆元定理 3 設(shè)m是一個(gè)正整數(shù),(a,m)=1, 則存在a ,定理 4 設(shè)m1, m2N，(m1, m2) = 1，又設(shè)分別是模m1與m2的簡(jiǎn)化剩余系，則A = m1y m2x；xX，yY 是模m1m2的簡(jiǎn)化剩余系。定理5設(shè)m, nN，(m, n) = 1，則 (mn) = (m)(n) 證,由定理4直接得到定理 4 設(shè)m1, m2N，(m1, m2) = 1，又設(shè)定理6設(shè)n的標(biāo)準(zhǔn)分解式是n = 是它的全部素因數(shù)，則(n) = 證明:由定理5 有(n) = 對(duì)任意的素?cái)?shù)p，(p)等于數(shù)列1,

6、 2, , p中與p（也就是與p）互素的整數(shù)的個(gè)數(shù)，因此(p) = p (1)定理6設(shè)n的標(biāo)準(zhǔn)分解式是n = 是它的全部素因又n = ,和(1)式結(jié)合起來(lái)就得到結(jié)論推論 設(shè)pq是不同的素?cái)?shù),則(pq) = (p) (q) =(p-1)(q-1)下面進(jìn)一步考察歐拉函數(shù)的性質(zhì)又n = ,和(1)式結(jié)合起來(lái)就得到結(jié)論定理7 設(shè)n是一個(gè)正整數(shù) 則 證明: 設(shè)C=1,n, 按照與n的最大公因素分類(lèi),對(duì)d|n記 Cd=m|1m n,(m,n)=d,因?yàn)?(m,n)=d iff ,(m/d,n/d)=1,所以Cd中的元素m的形式Cd=m=dk|1k n/d,(k,n/d)=1,故Cd的元素個(gè)數(shù)為(n/d) ,因?yàn)槊總€(gè)整數(shù)屬于且僅屬于一個(gè)類(lèi)Cd因此,#C= ,即 , 又當(dāng)d遍歷n的正因素時(shí),n/d也遍歷n的所有正因素定理7 設(shè)n是一個(gè)正整數(shù) 則 例3 設(shè)整數(shù)n=50,利用定理8 對(duì)其進(jìn)行分類(lèi)解,因?yà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,