簡化剩余系與歐拉函數(shù).ppt

《簡化剩余系與歐拉函數(shù).ppt》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在應用文檔-天天文庫。

1、§3.3簡化剩余系與歐拉函數(shù)一、基本概念定義1設R是模m的一個剩余類，若有a?R，使得(a,m)=1，則稱R是模m的一個簡化剩余類。即與模m互質(zhì)的剩余類。注：若R是模的簡化剩余類，則R中的數(shù)都與m互素。例如，模4的簡化剩余類有兩個：R1(4)={?,?7,?3,1,5,9,?}，R3(4)={?,?5,?1,3,7,11,?}。定義2對于正整數(shù)k，令函數(shù)?(k)的值等于模k的所有簡化剩余類的個數(shù)，稱?(k)為Euler函數(shù)。容易驗證：?(2)=1，?(3)=2，?(4)=2，?(7)=6。注：?(m)就是在m的一個完全剩余系中與m互素的整數(shù)的個數(shù)，且定義3對于正整數(shù)m，從模m的每個簡化剩

2、余類中各取一個數(shù)xi，構(gòu)成一個集合{x1,x2,?,x?(m)}，稱為模m的一個簡化剩余系（或簡稱為簡化系）。注：由于選取方式的任意性，模m的簡化剩余系有無窮多個。例如，集合{9,?5,?3,?1}是模8的簡化剩余系；集合{1,3,5,7}也是模8的簡化剩余系.集合{1,3,5,7}稱為最小非負簡化剩余系。二、主要性質(zhì)定理1整數(shù)集合A是模m的簡化剩余系的充要條件是：①A中含有?(m)個整數(shù)；②A中的任何兩個整數(shù)對模m不同余；③A中的每個整數(shù)都與m互素。說明：簡化剩余系是某個完全剩余系中的部分元素構(gòu)成的集合，故滿足條件2；由定義1易知滿足條件3；由定義3易知滿足條件1。定理2設a是整數(shù)，(

3、a,m)=1，B={x1,x2,?,x?(m)}是模m的簡化剩余系，則集合A={ax1,ax2,?,ax?(m)}也是模m的簡化剩余系。證明顯然，集合A中有?(m)個整數(shù)。由于(a,m)=1，對于任意的xi（1?i??(m)），xi?B，有(axi,m)=(xi,m)=1。故A中的每一個數(shù)都與m互素。而且，A中的任何兩個不同的整數(shù)對模m不同余。因為，若有x?,x???B，使得ax??ax??(modm)，那么，x??x??(modm)，于是x?=x??。由以上結(jié)論及定理1可知集合A是模m的一個簡化系。注：在定理2的條件下，若b是整數(shù)，集合{ax1?b,ax2?b,,?,ax?(m)?b}

4、不一定是模m的簡化剩余系。例如，取m=4，a=1，b=1，以及模4的簡化剩余系{1,3}。但｛2，4｝不是模4的簡化剩余系。定理3設m1,m2?N，(m1,m2)=1，又設分別是模m1與m2的簡化剩余系，則A={m1y?m2x；x?X，y?Y}是模m1m2的簡化剩余系。證明由第二節(jié)定理3推論可知，若以X?與Y?分別表示模m1與m2的完全剩余系，使得X?X?，Y?Y?，則A?={m1y?m2x；x?X?，y?Y?}是模m1m2的完全剩余系。因此只需證明A?中所有與m1m2互素的整數(shù)的集合R即模m1m2的簡化剩余系是集合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。這說明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。因為m1與m2互素，所以(m2x?m1y,m1m2)=1，于是m2x?m1y?R。因此A?R。從而A=R。推論設m,n?N，(m,n)=1，則?(mn)=?(m)?(n)。證由定理3知，若x,y分別通過m,n的簡化剩余系，則my?nx通過mn的簡化剩余

6、系，即有my?nx通過?(mn)個整數(shù)。另一方面，x〔nx〕通過?(m)個整數(shù)，y〔my〕通過?(n)個整數(shù),從而my?nx通過?(m)?(n)個整數(shù)。故有?(mn)=?(m)?(n)。注：可以推廣到多個兩兩互質(zhì)數(shù)的情形。定理4設n是正整數(shù)，p1,p2,?,pk是它的全部素因數(shù)，證設n的標準分解式是由定理3推論得到對任意的素數(shù)p，?(p?)等于數(shù)列1,2,?,p?中與p?互素的整數(shù)的個數(shù)，從而定理得證。注：由定理4可知，?(n)=1的充要條件是n=1或2?？紤]有重素因子和沒有重素因子的情形。三、應用舉例注意：有重素因子時，上述不等式中等號不成立！例1設整數(shù)n?2，證明：即在數(shù)列1,2,?

7、,n中，與n互素的整數(shù)之和是證設在1,2,?,n中與n互素的個數(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