1、會計學1簡化剩余系與歐拉函數簡化剩余系與歐拉函數定義定義2 對于正整數對于正整數k，令函數，令函數 (k)的值等于模的值等于模k的所有的所有簡化剩余類的個數，稱簡化剩余類的個數，稱 (k)為為Euler函數。函數。容易驗證：容易驗證： (2) = 1， (3) = 2， (4) = 2， (7) = 6。注：注： (m)就是在就是在m的一個完全剩余系中與的一個完全剩余系中與m互素的互素的 整數的個數，且整數的個數，且 1().mm 定義定義3 對于正整數對于正整數m，從模，從模m的每個簡化剩余類中的每個簡化剩余類中 各取一個數各取一個數xi，構成一個集合，構成一個集合x1, x2, ,x (m

2、)， 稱為模稱為模m的一個簡化剩余系（或簡稱為簡化系）。的一個簡化剩余系（或簡稱為簡化系）。 第1頁/共19頁注：由于選取方式的任意性，模注：由于選取方式的任意性，模m的簡化剩余系的簡化剩余系有無窮多個。有無窮多個。例如，集合例如，集合9, 5, 3, 1是模是模8的簡化剩余系；的簡化剩余系； 集合集合1, 3, 5, 71, 3, 5, 7也是模也是模8 8的簡化剩余系的簡化剩余系. . 集合集合1, 3, 5, 71, 3, 5, 7稱為最小非負簡化剩余系。稱為最小非負簡化剩余系。 第2頁/共19頁二、主要性質二、主要性質 定理定理1 整數集合整數集合A是模是模m的簡化剩余系的充要條件是：

3、的簡化剩余系的充要條件是： A中含有中含有 (m)個整數；個整數； A中的任何兩個整數對模中的任何兩個整數對模m不同余；不同余； A中的每個整數都與中的每個整數都與m互素。互素。說明：簡化剩余系是某個完全剩余系中的部分元素說明：簡化剩余系是某個完全剩余系中的部分元素構成的集合，故滿足條件構成的集合，故滿足條件2； 由定義由定義1易知滿足條件易知滿足條件3；由定義由定義3 3易知滿足條件易知滿足條件1 1。第3頁/共19頁定理定理2 設設a是整數，是整數，(a, m) = 1，B = x1, x2, , x (m) 是模是模m的簡化剩余系，則集合的簡化剩余系，則集合 A = ax1, ax2,

4、, ax (m) 也是模也是模m的簡化剩余系。的簡化剩余系。證明證明 顯然，集合顯然，集合A中有中有 (m)個整數。個整數。 由于由于(a, m) = 1， 對于任意的對于任意的xi（1 i (m)），xi B， 有有(axi, m) = (xi, m) = 1。 故故A中的每一個數都與中的每一個數都與m互素。互素。 而且，而且，A中的任何兩個不同的整數對模中的任何兩個不同的整數對模m不同余。不同余。 因為，若有因為，若有x , x B，使得，使得 a x ax (mod m)，那么，那么， x x (mod m)， 于是于是x = x 。 由以上結論及定理由以上結論及定理1可知集合可知集合A

5、是模是模m的一個簡化系。的一個簡化系。 第4頁/共19頁注：在定理注：在定理2的條件下，若的條件下，若b是整數，集合是整數，集合ax1 b, ax2 b, , ax (m) b不一定是模不一定是模m的簡化剩余系。的簡化剩余系。 例如，取例如，取m = 4，a = 1，b = 1， 以及模以及模4的簡化剩余系的簡化剩余系1, 3。但但2 2，4 4不是模不是模4 4的簡化剩余系。的簡化剩余系。第5頁/共19頁定理定理3 設設m1, m2 N，(m1, m2) = 1，又設，又設1212()12(),mmXx xxYyyy與與分別是模分別是模m1與與m2的簡化剩余系，的簡化剩余系， 則則 A =

6、m1y m2x；x X，y Y 是模是模m1m2的簡化剩余系。的簡化剩余系。證明證明 由第二節定理由第二節定理3 3推論可知，推論可知， 若以若以X 與與Y 分別表示分別表示 模模m1與與m2的完全剩余系，使得的完全剩余系，使得X X ，Y Y ， 則則A = m1y m2x；x X ，y Y 是模是模m1m2的完全的完全 剩余系。剩余系。 因此只需證明因此只需證明A 中所有與中所有與m1m2互素的整數的集合互素的整數的集合R 即模即模m1m2的簡化剩余系是集合的簡化剩余系是集合A。 第6頁/共19頁若若m1y m2x R，則，則(m1y m2x, m1m2) = 1， 所以所以(m1y m2

7、x, m1) = 1， 于是于是 (m2x, m1) = 1，(x, m1) = 1，x X。同理可得到同理可得到y 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。 從而從而

8、A = R。 第7頁/共19頁推論推論 設設m, n N，(m, n) = 1，則，則 (mn) = (m) (n)。證證 由定理由定理3知，若知，若x,y分別通過分別通過m , n的簡化剩余系，的簡化剩余系， 則則my nx通過通過mn的簡化剩余系，的簡化剩余系， 即有即有 my nx通過通過 (mn)個整數。個整數。 另一方面，另一方面，xnx通過通過 (m)個整數，個整數， ymy通過通過 (n)個整數個整數, 從而從而my nx通過通過 (m) (n)個整數。個整數。故有故有 (mn) = (m) (n)。注：可以推廣到多個兩兩互質數的情形。注：可以推廣到多個兩兩互質數的情形。第8頁/

9、共19頁定理定理4 設設n是正整數，是正整數，p1, p2, , pk是它的全部素因數，是它的全部素因數， |121111( )(1)(1)(1)1.()pnknnnpppp 則則證證 設設n的標準分解式是的標準分解式是 1ikiinp 由定理由定理3 3推論得到推論得到 1( )()ikiinp 對任意的素數對任意的素數p， (p )等于數列等于數列1, 2, , p 中與中與p 互素的整數的個數，互素的整數的個數， 11()1()pppppppp 因因此此，從而定理得證。從而定理得證。14( )1,()THnnpnp 即即為為：為為 的的質質因因數數. .第9頁/共19頁注：由定理注：由定

10、理4可知，可知， (n) = 1的充要條件是的充要條件是n = 1或或2。1kiinp 因因為為111111( )111()()()kkkkiiiiiiiinnpppp 考慮有重素因子和沒有重素因子的情形。考慮有重素因子和沒有重素因子的情形。 三、應用舉例三、應用舉例注意：有重素因子時，上述不等式中等號不成立！注意：有重素因子時，上述不等式中等號不成立！第10頁/共19頁例例1 設整數設整數n 2，證明：，證明： 1( , ) 11( ).2i ni ninn 即在數列即在數列1, 2, , n中，與中，與n互素的整數之和是互素的整數之和是 1( ).2nn 證證 設在設在1, 2, , n中

11、與中與n互素的互素的個數是個數是 (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) 1( ).2nn 與集合與集合n a1, n a2, , n a (n)是相同的，是相同的，第11頁/共19頁例例2 設設n N，證明：，證明：1) 若若n是奇數，則是奇數，則

12、 (4n) = 2 (n)；的充要條件是的充要條件是n = 2k，k N；12) ( )2nn 的充要條件是的充要條件是n = 2k3l，k, l N；13) ( )3nn 4) 若若6 n，則，則 (n) 13n 5) 若若n 1與與n 1都是素數，都是素數，n 4，則，則 (n) 13n 第12頁/共19頁1) 若若n是奇數，則是奇數，則 (4n) = 2 (n)； (4n) = (22n)= (22) (n)= 2 (n)TH414( )1,()THnnpnp 為為 的的質質因因數數. .第13頁/共19頁的充要條件是的充要條件是n = 2k，k N；12) ( )2nn 若若n = 2

13、k， 1(2 ) TH4 212()kk 則則12k 12n 若若 (n) = 12n設設n = 2kn1， 12 n n12n 由由 (n) = (2kn1) = (2k) (n1) =2k 1 (n1) 1111()22knnn 111()2nnn 11()nn 所以所以n1 = 1，即，即n = 2k；第14頁/共19頁的充要條件是的充要條件是n = 2k3l，k, l N；13) ( )3nn 111213 1233() ()kln1( ),3nn 若若設設 n = 2k3ln1， 112,3nn n n11( )(2 3)3klnnn由由1(2 ) (3 ) ()kln 11()nn

14、 所以所以n1 = 1，即，即n = 2k3l；若若 n = 2k3l，則則 (n) = (2k) (3l)111()3nnn 第15頁/共19頁4) 若若6 n，則，則 (n) 13n 設設 n = 2k3ln1， 16,n則則 (n) = (2k) (3l) (n1) 13n 112 3()3kln 112 33kln 第16頁/共19頁5) 若若n 1與與n 1都是素數，都是素數，n 4，則，則 (n) 13n 因為因為n 4，且，且n 1與與n 1都是奇素數，都是奇素數， 所以所以n是偶數，且是偶數，且n 1 3.所以所以n 1與與n 1都不等于都不等于3，所以所以3 n，由結論由結論4，也不能被也不能被3 3整除，整除，因此因此6 n。即可得到結論即可得到結論5 5。若若6 n，則，則