简化剩余系与欧拉函数

1、3.3 3.3 简化剩余系与欧拉函数简化剩余系与欧拉函数 一、基本概念一、基本概念定义定义1 设设R是模是模m的一个剩余类，若有的一个剩余类，若有a R，使得，使得(a, m)= 1，则称，则称R是模是模m的一个简化剩余类的一个简化剩余类。即与模即与模m互质的剩余类。互质的剩余类。 注：若注：若R是模的简化剩余类，则是模的简化剩余类，则R中的数都与中的数都与m互素。互素。例如，模例如，模4的简化剩余类有两个：的简化剩余类有两个：R1(4) = , 7 , 3, 1 , 5 , 9 , ，R3(4) = , 5 , 1 , 3 , 7 , 11 , 。定义定义2 对于正整数对于正整数k，令函数，

2、令函数 (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)， 称为模称为模m的一个简化剩余系（或简称为简化系）。的一个简化剩余系（或简称为简化系）。

3、 注：由于选取方式的任意性，模注：由于选取方式的任意性，模m的简化剩余系的简化剩余系有无穷多个。有无穷多个。例如，集合例如，集合9, 5, 3, 1是模是模8的简化剩余系；的简化剩余系； 集合集合1, 3, 5, 71, 3, 5, 7也是模也是模8 8的简化剩余系的简化剩余系. . 集合集合1, 3, 5, 71, 3, 5, 7称为最小非负简化剩余系。称为最小非负简化剩余系。 二、主要性质二、主要性质 定理定理1 整数集合整数集合A是模是模m的简化剩余系的充要条件是：的简化剩余系的充要条件是： A中含有中含有 (m)个整数；个整数； A中的任何两个整数对模中的任何两个整数对模m不同余；不同

4、余； A中的每个整数都与中的每个整数都与m互素。互素。说明：简化剩余系是某个完全剩余系中的部分元素说明：简化剩余系是某个完全剩余系中的部分元素构成的集合，故满足条件构成的集合，故满足条件2； 由定义由定义1易知满足条件易知满足条件3；由定义由定义3 3易知满足条件易知满足条件1 1。定理定理2 设设a是整数，是整数，(a, m) = 1，B = x1, x2, , x (m) 是模是模m的简化剩余系，则集合的简化剩余系，则集合 A = ax1, ax2, , ax (m) 也是模也是模m的简化剩余系。的简化剩余系。证明证明 显然，集合显然，集合A中有中有 (m)个整数。个整数。 由于由于(a,

5、 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是模是模m的一个简化系。的一个简化系。 注：在定理注：在定理2的条件下，若的条件下，若b是整数，集合是整数，集合ax1 b, ax2 b,

6、, ax (m) b不一定是模不一定是模m的简化剩余系。的简化剩余系。 例如，取例如，取m = 4，a = 1，b = 1， 以及模以及模4的简化剩余系的简化剩余系1, 3。但但2 2，4 4不是模不是模4 4的简化剩余系。的简化剩余系。定理定理3 设设m1, m2 N，(m1, m2) = 1，又设，又设1212()12(),mmXx xxYyyy 与与分别是模分别是模m1与与m2的简化剩余系，的简化剩余系， 则则 A = m1y m2x；x X，y Y 是模是模m1m2的简化剩余系。的简化剩余系。证明证明 由第二节定理由第二节定理3 3推论可知，推论可知， 若以若以X 与与Y 分别表示分别

7、表示 模模m1与与m2的完全剩余系，使得的完全剩余系，使得X X ，Y Y ， 则则A = m1y m2x；x X ，y Y 是模是模m1m2的完全的完全 剩余系。剩余系。 因此只需证明因此只需证明A 中所有与中所有与m1m2互素的整数的集合互素的整数的集合R 即模即模m1m2的简化剩余系是集合的简化剩余系是集合A。 若若m1y m2x R，则，则(m1y m2x, m1m2) = 1， 所以所以(m1y m2x, m1) = 1， 于是于是 (m2x, m1) = 1，(x, m1) = 1，x X。同理可得到同理可得到y Y，因此，因此m1y m2x A。 这说明这说明R A。 另一方面，

8、若另一方面，若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的简化剩余系，的简化

9、剩余系， 则则my nx通过通过mn的简化剩余系，的简化剩余系， 即有即有 my nx通过通过 (mn)个整数。个整数。 另一方面，另一方面，xnx通过通过 (m)个整数，个整数， ymy通过通过 (n)个整数个整数, 从而从而my nx通过通过 (m) (n)个整数。个整数。故有故有 (mn) = (m) (n)。注：可以推广到多个两两互质数的情形。注：可以推广到多个两两互质数的情形。定理定理4 设设n是正整数，是正整数，p1, p2, , pk是它的全部素因数，是它的全部素因数， |121111( )(1)(1)(1)1.()pnknnnpppp 则则证证 设设n的标准分解式是的标准分解式

10、是 1ikiinp 由定理由定理3 3推论得到推论得到 1( )()ikiinp 对任意的素数对任意的素数p， (p )等于数列等于数列1, 2, , p 中与中与p 互素的整数的个数，互素的整数的个数， 11()1()pppppppp 因因此此，从而定理得证。从而定理得证。14( )1,()THnnpnp 即即为为：为为 的的质质因因数数. .注：由定理注：由定理4可知，可知， (n) = 1的充要条件是的充要条件是n = 1或或2。1kiinp 因因为为111111( )111()()()kkkkiiiiiiiinnpppp 考虑有重素因子和没有重素因子的情形。考虑有重素因子和没有重素因子

11、的情形。 三、应用举例三、应用举例注意：有重素因子时，上述不等式中等号不成立！注意：有重素因子时，上述不等式中等号不成立！例例1 设整数设整数n 2，证明：，证明： 1( , ) 11( ).2i ni ninn 即在数列即在数列1, 2, , n中，与中，与n互素的整数之和是互素的整数之和是 1( ).2nn 证证 设在设在1, 2, , n中与中与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

12、)故故 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)是相同的，是相同的，例例2 设设n N，证明：，证明：1) 若若n是奇数，则是奇数，则 (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，

13、则，则 (n) 13n 1) 若若n是奇数，则是奇数，则 (4n) = 2 (n)； (4n) = (22n)= (22) (n)= 2 (n)TH414( )1,()THnnpnp 为为 的的质质因因数数. .的充要条件是的充要条件是n = 2k，k N；12) ( )2nn 若若n = 2k， 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 = 2

14、k；的充要条件是的充要条件是n = 2k3l，k, l N；13) ( )3nn 111213 1233() ()kln 1( ),3nn 若若设设 n = 2k3ln1， 112,3nn n n11( )(2 3)3klnnn由由1(2 ) (3 ) ()kln 11()nn 所以所以n1 = 1，即，即n = 2k3l；若若 n = 2k3l，则则 (n) = (2k) (3l)111()3nnn 4) 若若6 n，则，则 (n) 13n 设设 n = 2k3ln1， 16,n则则 (n) = (2k) (3l) (n1) 13n 112 3()3kln 112 33kln 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。即可得