資源描述：
《簡(jiǎn)化剩余系與歐拉函數(shù).ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫(kù)。
1、§3.3簡(jiǎn)化剩余系與歐拉函數(shù)一、基本概念定義1設(shè)R是模m的一個(gè)剩余類(lèi)，若有a?R，使得(a,m)=1，則稱(chēng)R是模m的一個(gè)簡(jiǎn)化剩余類(lèi)。即與模m互質(zhì)的剩余類(lèi)。注：若R是模的簡(jiǎn)化剩余類(lèi)，則R中的數(shù)都與m互素。例如，模4的簡(jiǎn)化剩余類(lèi)有兩個(gè)：R1(4)={?,?7,?3,1,5,9,?}，R3(4)={?,?5,?1,3,7,11,?}。定義2對(duì)于正整數(shù)k，令函數(shù)?(k)的值等于模k的所有簡(jiǎn)化剩余類(lèi)的個(gè)數(shù)，稱(chēng)?(k)為Euler函數(shù)。容易驗(yàn)證：?(2)=1，?(3)=2，?(4)=2，?(7)=6。注：?(m)就是在m的一個(gè)完全剩余系中與m互素的整數(shù)的個(gè)數(shù)，且定義3對(duì)于正整數(shù)m，從模m的每個(gè)簡(jiǎn)化剩
2、余類(lèi)中各取一個(gè)數(shù)xi，構(gòu)成一個(gè)集合{x1,x2,?,x?(m)}，稱(chēng)為模m的一個(gè)簡(jiǎn)化剩余系（或簡(jiǎn)稱(chēng)為簡(jiǎn)化系）。注：由于選取方式的任意性，模m的簡(jiǎn)化剩余系有無(wú)窮多個(gè)。例如，集合{9,?5,?3,?1}是模8的簡(jiǎn)化剩余系；集合{1,3,5,7}也是模8的簡(jiǎn)化剩余系.集合{1,3,5,7}稱(chēng)為最小非負(fù)簡(jiǎn)化剩余系。二、主要性質(zhì)定理1整數(shù)集合A是模m的簡(jiǎn)化剩余系的充要條件是：①A中含有?(m)個(gè)整數(shù)；②A中的任何兩個(gè)整數(shù)對(duì)模m不同余；③A中的每個(gè)整數(shù)都與m互素。說(shuō)明：簡(jiǎn)化剩余系是某個(gè)完全剩余系中的部分元素構(gòu)成的集合，故滿(mǎn)足條件2；由定義1易知滿(mǎn)足條件3；由定義3易知滿(mǎn)足條件1。定理2設(shè)a是整數(shù)，(
3、a,m)=1，B={x1,x2,?,x?(m)}是模m的簡(jiǎn)化剩余系，則集合A={ax1,ax2,?,ax?(m)}也是模m的簡(jiǎn)化剩余系。證明顯然，集合A中有?(m)個(gè)整數(shù)。由于(a,m)=1，對(duì)于任意的xi（1?i??(m)），xi?B，有(axi,m)=(xi,m)=1。故A中的每一個(gè)數(shù)都與m互素。而且，A中的任何兩個(gè)不同的整數(shù)對(duì)模m不同余。因?yàn)?，若有x?,x???B，使得ax??ax??(modm)，那么，x??x??(modm)，于是x?=x??。由以上結(jié)論及定理1可知集合A是模m的一個(gè)簡(jiǎn)化系。注：在定理2的條件下，若b是整數(shù)，集合{ax1?b,ax2?b,,?,ax?(m)?b}
4、不一定是模m的簡(jiǎn)化剩余系。例如，取m=4，a=1，b=1，以及模4的簡(jiǎn)化剩余系{1,3}。但｛2，4｝不是模4的簡(jiǎn)化剩余系。定理3設(shè)m1,m2?N，(m1,m2)=1，又設(shè)分別是模m1與m2的簡(jiǎn)化剩余系，則A={m1y?m2x；x?X，y?Y}是模m1m2的簡(jiǎn)化剩余系。證明由第二節(jié)定理3推論可知，若以X?與Y?分別表示模m1與m2的完全剩余系，使得X?X?，Y?Y?，則A?={m1y?m2x；x?X?，y?Y?}是模m1m2的完全剩余系。因此只需證明A?中所有與m1m2互素的整數(shù)的集合R即模m1m2的簡(jiǎn)化剩余系是集合A。若m1y?m2x?R，則(m1y?m2x,m1m2)=1，所以(m1
5、y?m2x,m1)=1，于是(m2x,m1)=1，(x,m1)=1，x?X。同理可得到y(tǒng)?Y，因此m1y?m2x?A。這說(shuō)明R?A。另一方面，若m1y?m2x?A，則x?X，y?Y，即(x,m1)=1，(y,m2)=1。由此及(m1,m2)=1得到(m2x?m1y,m1)=(m2x,m1)=1(m2x?m1y,m2)=(m1y,m2)=1。因?yàn)閙1與m2互素，所以(m2x?m1y,m1m2)=1，于是m2x?m1y?R。因此A?R。從而A=R。推論設(shè)m,n?N，(m,n)=1，則?(mn)=?(m)?(n)。證由定理3知，若x,y分別通過(guò)m,n的簡(jiǎn)化剩余系，則my?nx通過(guò)mn的簡(jiǎn)化剩余
6、系，即有my?nx通過(guò)?(mn)個(gè)整數(shù)。另一方面，x〔nx〕通過(guò)?(m)個(gè)整數(shù)，y〔my〕通過(guò)?(n)個(gè)整數(shù),從而my?nx通過(guò)?(m)?(n)個(gè)整數(shù)。故有?(mn)=?(m)?(n)。注：可以推廣到多個(gè)兩兩互質(zhì)數(shù)的情形。定理4設(shè)n是正整數(shù)，p1,p2,?,pk是它的全部素因數(shù)，證設(shè)n的標(biāo)準(zhǔn)分解式是由定理3推論得到對(duì)任意的素?cái)?shù)p，?(p?)等于數(shù)列1,2,?,p?中與p?互素的整數(shù)的個(gè)數(shù)，從而定理得證。注：由定理4可知，?(n)=1的充要條件是n=1或2?？紤]有重素因子和沒(méi)有重素因子的情形。三、應(yīng)用舉例注意：有重素因子時(shí)，上述不等式中等號(hào)不成立！例1設(shè)整數(shù)n?2，證明：即在數(shù)列1,2,?
7、,n中，與n互素的整數(shù)之和是證設(shè)在1,2,?,n中與n互素的個(gè)數(shù)是?(n)，a1,a2,?,a?(n)，(ai,n)=1，1?ai?n?1，1?i??(n)，則(n?ai,n)=1，1?n?ai?n?1，1?i??(n)，因此，集合{a1,a2,?,a?(n)}故a1?a2???a?(n)=(n?a1)?(n?a2)???(n?a?(n))，從而，2(a1?a2???a?(n))=n?(n)，因此a1?a2???a?(n)與集合{n
